Tag Archive for: adjacency list

Hierarchies with CTEs

Common table expressions (CTEs) have many applications. However, one of their capabilities to implement recursive queries is very useful for navigating and manipulating hierarchies.

Here is one brief example of utilizing that. Given a table with employees and their managers represented as adjacency list, provide list of employees that report to particular manager, ordered by the natural hierarchy order of listing each employee under the corresponding manager.

-- Create sample table with employees and managers

CREATE TABLE Employees(

 employee_nbr INT NOT NULL PRIMARY KEY,

 employee_name VARCHAR(35),

 manager_nbr INT NULL REFERENCES Employees(employee_nbr));

 

INSERT INTO Employees VALUES (1, 'John Doe', NULL);

INSERT INTO Employees VALUES (2, 'James Brown', 1);

INSERT INTO Employees VALUES (3, 'Keith Green', NULL);

INSERT INTO Employees VALUES (4, 'Peter Roth', 2);

INSERT INTO Employees VALUES (5, 'Hans Gruber', 2);

INSERT INTO Employees VALUES (6, 'Kris Evans', 4);

INSERT INTO Employees VALUES (7, 'Jeff Colleman', NULL);

 

-- Use recursive CTE to build binary and charachter paths

WITH EmployeeHierarchy

AS

(SELECT employee_nbr, employee_name, manager_nbr,

        CAST(employee_nbr AS VARBINARY(MAX)) AS bpath,

        CAST('.' +

            CAST(employee_nbr AS VARCHAR(4)) +

            '.' AS VARCHAR(MAX)) AS cpath

 FROM Employees

 WHERE manager_nbr IS NULL

 UNION ALL

 SELECT E.employee_nbr, E.employee_name, E.manager_nbr,

        H.bpath + CAST(E.employee_nbr AS BINARY(4)),

        H.cpath + CAST(E.employee_nbr AS VARCHAR(4)) + '.'

 FROM Employees AS E

 JOIN EmployeeHierarchy AS H

   ON E.manager_nbr = H.employee_nbr)

SELECT employee_nbr, employee_name, manager_nbr, bpath, cpath

FROM EmployeeHierarchy

WHERE cpath LIKE '%.2.%' -- filter all employees for manager 2

ORDER BY bpath;          -- order by natural hierarchy path

 

-- Results

employee_nbr employee_name  manager_nbr bpath                              cpath

------------ -------------- ----------- ---------------------------------- ----------

2            James Brown    1           0x0000000100000002                .1.2.

4            Peter Roth    2           0x000000010000000200000004        .1.2.4.

6            Kris Evans    4           0x00000001000000020000000400000006 .1.2.4.6.

5            Hans Gruber    2           0x000000010000000200000005        .1.2.5.

The method above creates two manager/employee paths: a binary path that preserves the natural ordering at each level, which can be used to sort; a character path that can be used to filter by manager.

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