How to find all nodes in a subtree in a recursive SQL query?

Question

I have a table which defines a child-parent relationship between nodes:

CREATE TABLE node (                           ' pseudo code alert
  id        INTEGER PRIMARY KEY,
  parentID  INTEGER, ' should be a valid id.
)

If parentID always points to a valid existing node, then this will naturally define a tree structure.

If the parentID is NULL then we may assume that the node is a root node.

How would I:

1. Find all the nodes which are decendents of a given node?
2. Find all the nodes under a given node to a specific depth?

I would like to do each of these as a single SQL (I expect it would necessarily be recursive) or two mutually recursive queries.

I'm doing this in an ODBC context, so I can't rely on any vendor specific features.

Edit

• No tables are written yet, so adding extra columns/tables is perfectly acceptable.
• The tree will potentially be updated and added to quite often; auxillary data structures/tables/columns would be possible, though need to be kept up-to-date. If you have any magic books you reach for for this kind of query, I'd like to know.

Many thanks.

Answer 1

Some methods were covered previously in this article:

SQL - how to store and navigate hierarchies

Answer 2

If you have any magic books you reach for for this kind of query, I'd like to know.

Celko's Trees and Hierarchies in SQL For Smarties

Answer 3

This link provides a tutorial on both the Adjacency List Model (as described in the question), and the Nested Set Model. It is written as part of the documentation for MySQL.

What is not discussed in that article is insertion/delection time, and maintenance cost of the two approaches. For example:

• a dynamically grown tree using the Nested Set Model would seem to need some maintenance to maintain the nesting (e.g. renumbering all left and right set numbers)
• removal of a node in the adjacency list model would require updates in at least one other row.

Answer 4

Store the entire "path" from the root node's ID in a separate column, being sure to use a separator at the beginning and end as well. E.g. let's say 1 is the parent of 5, which is the parent of 17, and your separator character is dash, you would store the value -1-5-17- in your path column.

Now to find all children of 5 you can simply select records where the path includes -5-

The separators at the ends are necessary so you don't need to worry about ID's that are at the leftmost or rightmost end of the field when you use LIKE.

As for your depth issue, if you add a depth column to your table indicating the current nesting depth, this becomes easy as well. You look up your starting node's depth and then you add x to it where x is the number of levels deep you want to search, and you filter out records with greater depth than that.