Joe Celko's SQL for Smarties, 3rd Edition

30.3. Acyclic Graphs as Nested Sets

Let’s start with a simple graph in an adjacency list model.

INSERT INTO Nodes (node_id)
VALUES ('a'), ('b'), ('c'), ('d'),
       ('e'), ('f'), ('g'), ('h');

INSERT INTO AdjacencyListGraph (begin_node_id, end_node_id)
VALUES ('a', 'b'), ('a', 'c'), ('b', 'd'), ('c', 'd'),
       ('c', 'g'), ('d', 'e'), ('d', 'f'), ('e', 'h'),
       ('g', 'h');

We can convert this adjacency list model to the nested sets model (see Figure 30.1) with a simple stack algorithm:

-- Stack to keep track of nodes being traversed in depth-first fashion CREATE TABLE NodeStack (node_id INTEGER NOT NULL PRIMARY KEY REFERENCES Nodes (node_id), distance INTEGER NOT NULL CHECK (distance >= 0), lft INTEGER CHECK (lft >= 1), rgt INTEGER, CHECK (rgt > lft)); CREATE ...