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

5 replies
  1. Plamen Ratchev
    Plamen Ratchev says:

    Hi mrbinky3000,

    Here is one method to convert adjacency list to nested sets (credit goes to Itzik Ben-Gan):

    WITH Nums AS (
    SELECT n FROM(VALUES(1),(2)) AS T(n)),
    SortPath AS (
    SELECT node, 0 AS lvl, n,
    CAST(n AS VARBINARY(MAX)) AS sort_path
    FROM AdjacencyList
    CROSS JOIN Nums
    WHERE parent IS NULL
    UNION ALL
    SELECT A.node, P.lvl + 1, N.n,
    P.sort_path + CAST(
    ROW_NUMBER() OVER(PARTITION BY A.parent
    ORDER BY A.node, N.n)
    AS BINARY(4))
    FROM SortPath AS P
    JOIN AdjacencyList AS A
    ON P.n = 1
    AND A.parent = P.node
    CROSS JOIN Nums AS N),
    Sort AS (
    SELECT node, lvl,
    ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval
    FROM SortPath),
    NS AS (
    SELECT node, lvl, MIN(sortval) AS lf, MAX(sortval) AS rg
    FROM Sort
    GROUP BY node, lvl)
    SELECT A.node, NS.lvl, NS.lf, NS.rg
    FROM NS
    JOIN AdjacencyList AS A
    ON A.node = NS.node;

    Reply
  2. Paul Russo
    Paul Russo says:

    Cool – thanks – works a treat – once I had the adjacency list I pulled that out as a digraph (DOT format) – easy to feed into a tool such as Graphviz and bingo – your nested set is drawn as a diagram – good to check visually that your structure is held properly. Many thanks again!

    Reply

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published.