使用 SQLite 递归公用表表达式来遍历具有嵌入树的树

Question

我有一个代表元素树的表格。可以将一棵树嵌入到一棵树中。

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;

“Parent”列保存对元素父级的引用，“EmbeddedTree”列保存对应嵌入的树的引用。

以下是示例数据集：

--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;

我现在的目标是使用递归 CTE 来获取飞机的所有元素。

我读到了 SQLite 的 CTE (https://www.sqlite.org/draft/lang_with.html)，但只能获取树的“直接”成员，但不包括树的完整结构嵌入树木。 我用过

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

并且得到了

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

但我需要的是扩展结果表，包含左右发动机的温度成员

| 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 |

谁可以帮助正确扩展递归 CTE 以获得所需（或类似）的结果？

Answer 1

我自己的问题有了答案： 解决方案是结合两个递归 CTE，如下所示：

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

产生所需的结果，看起来像

| 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   |

注意：在第二个递归 CTE 的末尾有一个

ORDER BY 2 DESC

定义遍历顺序是 DFS 还是 BFS 的语句（不带“DESC”）