Convert an adjacency list (parent / child) model into a nested set model

The adjacency list model uses child/parent linking column to handle hierarchies.

The nested set model is to number the nodes according to a tree traversal, which visits each node twice, assigning numbers in the order of visiting, and at both visits. This leaves two numbers for each node, which are stored as two attributes. Querying becomes inexpensive: hierarchy membership can be tested by comparing these numbers. Updating requires renumbering and is therefore expensive.

To convert an adjacency list model into a nested set model, use a push down stack algorithm. Assume that we have these tables:

-- Tree holds the adjacency model
CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
 boss CHAR(10));

INSERT INTO Tree
SELECT emp, boss FROM Personnel;

-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
 emp CHAR(10) NOT NULL,
 lft INTEGER,
 rgt INTEGER);

BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;

SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;

INSERT INTO Stack
SELECT 1, emp, 1, NULL
 FROM Tree
 WHERE boss IS NULL;

DELETE FROM Tree
 WHERE boss IS NULL;

WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
 FROM Stack AS S1, Tree AS T1
 WHERE S1.emp = T1.boss
 AND S1.stack_top = current_top)
 THEN
 BEGIN -- push when top has subordinates, set lft value
 INSERT INTO Stack
 SELECT (current_top + 1), MIN(T1.emp), counter, NULL
 FROM Stack AS S1, Tree AS T1
 WHERE S1.emp = T1.boss
 AND S1.stack_top = current_top;

 DELETE FROM Tree
 WHERE emp = (SELECT emp
 FROM Stack
 WHERE stack_top = current_top + 1);

 SET counter = counter + 1;
 SET current_top = current_top + 1;
 END
 ELSE
 BEGIN -- pop the stack and set rgt value
 UPDATE Stack
 SET rgt = counter,
 stack_top = -stack_top -- pops the stack
 WHERE stack_top = current_top
 SET counter = counter + 1;
 SET current_top = current_top - 1;
 END IF;
 END LOOP;
END;

Although this procedure works, you might want to use a language that has arrays in it, instead of trying to stick to pure SQL.

Joe Celko is an Atlanta-based independent consultant. He is the author of Instant SQL Programming (Wrox Press, 1997). You can contact him at www.celko.com