Suppose a tree structure is implemented in SQL like this:
CREATE TABLE nodes (
id INTEGER PRIMARY KEY,
parent INTEGER -- references nodes(id)
);
Although cycles can be created in this representation, let's assume we never let that happen. The table will only store a collection of roots (records where parent is null) and their descendants.
The goal is to, given an id of a node on the table, find all nodes that are descendants of it.
A is a descendant of B if either A's parent is B or A's parent is a descendant of B. Note the recursive definition.
Here is some sample data:
INSERT INTO nodes VALUES (1, NULL);
INSERT INTO nodes VALUES (2, 1);
INSERT INTO nodes VALUES (3, 2);
INSERT INTO nodes VALUES (4, 3);
INSERT INTO nodes VALUES (5, 3);
INSERT INTO nodes VALUES (6, 2);
which represents:
1
`-- 2
|-- 3
| |-- 4
| `-- 5
|
`-- 6
We can select the (immediate) children of 1 by doing this:
SELECT a.* FROM nodes AS a WHERE parent=1;
We can select the children and grandchildren of 1 by doing this:
SELECT a.* FROM nodes AS a WHERE parent=1
UNION ALL
SELECT b.* FROM nodes AS a, nodes AS b WHERE a.parent=1 AND b.parent=a.id;
We can select the children, grandchildren, and great grandchildren of 1 by doing this:
SELECT a.* FROM nodes AS a WHERE parent=1
UNION ALL
SELECT b.* FROM nodes AS a, nodes AS b WHERE a.parent=1 AND b.parent=a.id
UNION ALL
SELECT c.* FROM nodes AS a, nodes AS b, nodes AS c WHERE a.parent=1 AND b.parent=a.id AND c.parent=b.id;
How can a query be constructed that gets all descendants of node 1 rather than those at a finite depth? It seems like I would need to create a recursive query or something.
I'd like to know if such a query would be possible using SQLite. However, if this type of query requires features not available in SQLite, I'm curious to know if it can be done in other SQL databases.
