Convert an adjacency list model into a nested set model

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