SQL select descendants of a row

Question

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

Answer 1

Some databases allow that using recursive common table expressions, but not SQLite.

You could consider changing your table definition. With a table like this, it's easy to query all descendants of 1:

id (varchar)
--------------
001
001002
001002003
001002003004
001002003005
001002006

This allows you to query all descendants of 1 like:

SELECT * FROM YourTable WHERE id LIKE '001%'

It sounds a bit whacky, but works very well in practice.

Answer 2

The way you've set up your schema doesn't really suit itself very well to the relational model (as you've discovered). But there is another way that may not be so obvious at first, but is much more flexible. It's called a "nested set model" and it just structures things slightly differently.

Managing Hierarchical Data in MySQL (look for the section "The Nested Set Model") shows how to do this in MySQL, but it should translate to SQLite fairly easily. I won't go into too much detail here, because that article is actually pretty long, but it should give you all you need to get going.