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