As you will recall from my previous article, the usual example of a tree
structure in SQL books is called an adjacency list model and it looks like this:
Another way of representing trees is to show them as nested sets. Since
SQL is a set oriented language, this is a better model than the usual
adjacency list approach you see in most text books. Let us define a simple
Personnel table like this, ignoring the left (lft) and right (rgt) columns
for now. This problem is always given with a column for the employee and
one for his boss in the textbooks. This table without the lft and rgt
columns is called the adjacency list model, after the graph theory
technique of the same name; the pairs of nodes are adjacent to each other.
The organizational chart would look like this as a directed graph:
To show a tree as nested sets, replace the nodes with ovals, then nest
subordinate ovals inside each other. The root will be the largest oval and
will contain every other node. The leaf nodes will be the innermost ovals
with nothing else inside them and the nesting will show the hierarchical
relationship. The rgt and lft columns (I cannot use the reserved words
LEFT and RIGHT in SQL) are what shows the nesting.
To convert the graph into a nested sets model think of a little worm
crawling along the tree. The worm starts at the top, the root, makes a
complete trip around the tree. When he comes to a node, he puts a number
in the cell on the side that he is visiting and increments his counter.
Each node will get two numbers, one of the right side and one for the
left. Computer Science majors will recognize this as a modified preorder
tree traversal algorithm.
The code for implementing this in T-SQL is a straigh...
To continue reading for free, register below or login
To read more you must become a member of SearchOracle.com
t forward stack
implementation. First, let's load up some data into a tree table and then
create a stack table. I will explain how the stack works in a minute.
Each row of the stack holds the nested set (lft, rgt) pair, the node value
(emp) and an integer that represents the current top of the stack as an
integer. When the stack_top is positive, something has been pushed onto
the stack. When the stack_top is negative, it has been popped off the
stack.
The algorithm is pretty straight forward, though there are some tricks
about representing a stack in T-SQL. Here is what we know:
-
We will do (2 * (SELECT COUNT(*) FROM Tree)) operation to build the
(lft, rgt) pairs for each node. We need a general counter for this.
-
When a node is pushed on the stack, we give it a lft number and
increment the counter.
-
When a node is popped from the stack, we give it a rgt number and
increment the counter.
-
We start at the root. Each nodes goes on and off the stack once and
only once.
-
We look at the top of the stack and push the youngest subordinate of
that node onto the stack
-
When the node on the top of stack is a leaf node or a node without
"un-popped" subordinates back in the tree, pop it off the stack.
Here is the code in T-SQL:
Note that the leftover stack_top numbers are the negatives of the depth of
their node in the original tree. Also, notice that the original tree is
being destroyed in this procedure; you might want to save and use a copy in
a temporary table instead.
About the Author
Joe Celko is author of SQL for Smarties: Advanced SQL Programming (Morgan-Kaufmann, 1999).
