The 'obvious' representation of a tree in a relational database uses relations to represent edges in the graph.
This is called out in
SqlAntiPatterns, since a naive implementation of tree traversal then has to make many queries, typically one per node.
TreeInSql solves this by changing the representation.
If you have a procedural language driving the database then there is another way which does not change the representation. The trick is to process tree nodes in breadth-first order. After processing a level in the tree, the next level is selected en masse. Tree traversal can then be done with a number of queries proportional to the depth of the tree. Alternatively levels of the tree are accumulated into a temporary table for further processing.
This algorithm can be adapted to traverse
DirectedAcyclicGraphs (but then needs
SelectDistinct), or to traverse arbitrary
DirectedGraphs (but then needs an in-memory or in-database visited flag to avoid visiting the same node twice).
EditHint: Merge with
TreeInSql? Not sure about that - it might be better to move the bulk of
TreeInSql to a new page
FullPathStoredAtLeaves and have
TreeInSql refer there and here and to whatever other schemes people have for dealing with graph representation in
SqlLanguage.