sqliterecursiontreecommon-table-expression

Use a SQLite Recursive Common Table Expression to walk a Tree with embedded Trees


I have a table which represents a tree of elements. It is possible to embed a tree into a tree.

CREATE TABLE ELEMENTS(
    ElementName TEXT PRIMARY KEY,
    Parent TEXT NULLABLE,
    EmbeddedTree TEXT NULLABLE, 
    FOREIGN KEY(Parent) REFERENCES ELEMENTS(ElementName),
    FOREIGN KEY(EmbeddedTree) REFERENCES ELEMENTS(ElementName))
WITHOUT ROWID;

Column 'Parent' holds the reference to an elements parent, and column 'EmbeddedTree' holds the reference to the tree which should be embedded.

Here are example data sets:

--First add a Tree-Structure 'Engine', which has a member 'Temperature':

BEGIN TRANSACTION;
INSERT INTO ELEMENTS(ElementName, Parent, EmbeddedTree)
 VALUES
 ('Engine', NULL, NULL),
 ('Engine.Temperature', 'Engine', NULL);

--Second add a Tree-Structure 'Airplane', which embeds an 'Engine' on its left and right wing:
 
INSERT INTO ELEMENTS(ElementName, Parent, EmbeddedTree)
 VALUES
 ('Airplane', NULL, NULL),
 ('Airplane.EngineLeft', 'Airplane', (SELECT ElementName FROM ELEMENTS WHERE ElementName = 'Engine')),
 ('Airplane.EngineRight', 'Airplane', (SELECT ElementName FROM ELEMENTS WHERE ElementName = 'Engine'));

COMMIT;

My Goal now is to use a recursive CTE to get all elements of an Airplane.

I read about the CTE of SQLite (https://www.sqlite.org/draft/lang_with.html) but was just able to get the 'direct' members of a tree, but not including the full structure of the embedded trees. I used

WITH RECURSIVE 
    under_root(name, level, embeddedref, parent) AS
        (VALUES((SELECT ElementName from ELEMENTS WHERE ElementName = 'Airplane'), 0, NULL, NULL)
        UNION ALL
        SELECT ELEMENTS.ElementName,
        under_root.level + 1, 
        ELEMENTS.EmbeddedTree,
        ELEMENTS.Parent FROM ELEMENTS
        JOIN under_root ON ELEMENTS.Parent = under_root.name
        ORDER BY 2)
SELECT name, level, embeddedref, parent FROM under_root

and got

| name                 | level | embeddedref | parent   |
| Airplane             | 0     | NULL        | NULL     |
| Airplane.EngineLeft  | 1     | Engine      | Airplane |
| Airplane.EngineRight | 1     | Engine      | Airplane |

but i need is the extended result table, containing the temperature members of the left and right engine

| name                 | level | embeddedref | parent   |
| Airplane             | 0     | NULL        | NULL     |
| Airplane.EngineLeft  | 1     | Engine      | Airplane |
| Engine.Temperature   | 2     | NULL        | Engine   |
| Engine.Temperature   | 2     | NULL        | Engine   |
| Airplane.EngineRight | 1     | Engine      | Airplane |

Who can help to extend the recursive CTE properly to get the desired (or similar) result?


Solution

  • I have the answer to my own question: The solution is to combine two recursive CTE´s, which looks as follows:

    WITH RECURSIVE under_root(name, level, embeddedref, parent) AS
        (
            VALUES((SELECT ElementName from ELEMENTS WHERE ElementName = 'Airplane'), 0, NULL, NULL)
            UNION ALL
            SELECT ELEMENTS.ElementName,
            under_root.level + 1, 
            ELEMENTS.EmbeddedTree,
            ELEMENTS.Parent FROM ELEMENTS
            JOIN under_root ON ELEMENTS.Parent = under_root.name
            
            UNION ALL       
            SELECT ELEMENTS.ElementName,
            under_root.level + 1, 
            ELEMENTS.EmbeddedTree,
            ELEMENTS.Parent FROM ELEMENTS
            JOIN under_root ON ELEMENTS.Parent = under_root.embeddedref
            ORDER BY 2 DESC
        )
    SELECT name, level, embeddedref, parent FROM under_root
    

    which produces the desired result, which looks like

    | name                 | level | embeddedref | parent   |
    | Airplane             | 0     | NULL        | NULL     |
    | Airplane.EngineLeft  | 1     | Engine      | Airplane |
    | Engine.Temperature   | 2     | NULL        | Engine   |
    | Airplane.EngineRight | 2     | Engine      | Airplane |
    | Engine.Temperature   | 1     | NULL        | Engine   |
    

    Note: at the end of the second recursive CTE there is a

    ORDER BY 2 DESC
    

    statement which defines if the traversal order is DFS or BFS (without 'DESC')