SQL selects row children

Question

Assume that a tree structure is implemented in SQL:

CREATE TABLE nodes ( id INTEGER PRIMARY KEY, parent INTEGER -- references nodes(id) ); 

Although loops can be created in this view, suppose we never allow this. Only the collection of roots (records where the parent is null) and their descendants will be stored in the table.

The goal is to find all nodes that are descendants based on the node identifier in the table.

A is a descendant of B if the parent A B or A strong> parent is a descendant of B. Pay attention to the recursive definition.

Here are 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 (immediate) children 1 by doing the following:

 SELECT a.* FROM nodes AS a WHERE parent=1; 

We can select children and grandchildren 1 by following these steps:

 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 choose children, grandchildren and great-grandchildren 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 I build a query that receives all descendants of node 1 , and not at a fixed depth? It looks like I will need to create a recursive query or something else.

I would like to know if such a query is possible with SQLite. However, if this type of query requires functions that are not available in SQLite, I am curious to know if this can be done in other SQL databases.

Answer 1

Some databases allow the use of recursive generic table expressions, but not SQLLite.

You may consider changing the definition of the table. 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, for example:

 select * from YourTable where id like '001%' 

It sounds a little strange, but in practice it works very well.

Answer 2

The way you configure your schema is not well suited to a relational model (as you discovered). But there is another way that may not be so obvious at first, but much more flexible. It was called the “nested dialing model,” and it just structures things a little differently.

Managing hierarchical data in MySQL (see the "Nested Dialing Model" section) shows how to do this in MySQL, but this should easily translate SQLite. Here I will not go into details because this article is actually quite long, but it should give you everything you need.

Answer 3

Oracle has a CONNECT BY syntax that can be used for this, but, of course, it is specific to oracle.