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
Exactly what I was looking for. Thank you very much !
What about going the other way?
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;
The above sql seems to be incomplete and does not work.
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!