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?
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')