Breadth First Traversal In Sql

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.