Convert Tree Structure From Nested Set Into Adjacency List

Tree structures are often represented in nested set model or adjacency list model. In the nested set model each node has a left and right, where the root will always have a 1 in its left column and twice the number of nodes in its right column. On the other side the adjacency list model uses a linking column (child/parent) to handle hierarchies.

Sometimes there is a need to convert a nested set model into an adjacency list model. Here is one example of doing that:

CREATE TABLE NestedSet (
 node CHAR(1) NOT NULL PRIMARY KEY,
 lf INT NOT NULL,
 rg INT NOT NULL);
 
INSERT INTO NestedSet VALUES ('A', 1, 8);
INSERT INTO NestedSet VALUES ('B', 2, 3);
INSERT INTO NestedSet VALUES ('C', 4, 7);
INSERT INTO NestedSet VALUES ('D', 5, 6);
 
CREATE TABLE AdjacencyList (
 node CHAR(1) NOT NULL PRIMARY KEY,
 parent CHAR(1) NULL);
 
INSERT INTO AdjacencyList
SELECT A.node,
       B.node AS parent
FROM NestedSet AS A
LEFT OUTER JOIN NestedSet AS B
  ON B.lf = (SELECT MAX(C.lf)
             FROM NestedSet AS C
             WHERE A.lf > C.lf
               AND A.lf < C.rg);

-- Results
node    parent
------  --------
A       NULL
B       A
C       A
D       C

Additional resources:

Book: "Trees and Hierarchies in SQL for Smarties" by Joe Celko

Adjacency List Model
http://www.sqlsummit.com/AdjacencyList.htm

Trees in SQL
http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=1266295

Labels: , , , ,