Search all available nodes using SQL

Question

Suppose a table with two columns: From and To. Example:

From To 1 2 2 3 2 4 4 5 

I would like to know the most efficient way to find all nodes accessible from node using SQL Query. Example: taking 1 into account, it will return 2,3,4 and 5. You can use several queries combined by UNION clauses, but this would limit the number of levels that can be reached. Perhaps a different data structure will make the problem more accessible, but that is what is available.

I use Firebird, but I would like to have a solution that uses only standard SQL.

Answer 1

You can use a recursive generic table expression if you use most database brands, with the exception of MySQL and SQLite, as well as several other obscure ones (sorry, I find Firebird obscure). This syntax is an ANSI SQL standard, but Firebird does not yet support it.

Bugfix: Firebird 2.1 supports recursive CTEs, as @Hugues Van Landeghem comments.

Otherwise, see my presentation Models for hierarchical data with SQL for several different approaches.

For example, you can store additional lines for each path in your tree, and not just directly parent / child paths. I call this closing table.

 From To Length 1 1 0 1 2 1 1 3 2 1 4 2 1 5 3 2 2 0 2 3 1 2 4 1 3 3 0 4 4 0 4 5 1 5 5 0 

Now you can query SELECT * FROM MyTable WHERE From = 1 and get all the descendants of this node.

PS: I would not name the From column because it is a reserved SQL word.

Answer 2

Unfortunately, for this there is no good general solution that will work for all situations in all databases.

I recommend you look at these resources for MySQL solution:

• MySQL hierarchical data management
• Models for hierarchical data - a presentation by Bill Karvin that discusses this issue, demonstrates various solutions and compares the adjacency list model used with other alternative models.

For PostgreSQL and SQL Server, you should take a look at recursive CTEs .

If you use Oracle, you should look at CONNECT BY , which is a proprietary extension of SQL, which greatly simplifies the work with tree structures.

Answer 3

With standard SQL, the only way to store a tree with an acceptable read speed is to use a hack such as path enumeration. Please note that this is very difficult to write.

 ID PATH 1 1 2 1;2 3 1;2;3 4 1;2;4 SELECT * FROM tree WHERE path LIKE '%2;%'