THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

John Paul Cook

Modeling an Adjacency List Hierarchy with SQL Server 2017 Graph Database

The Northwind database implements the manager to employee hierarchy using an adjacency list, which is a type of graph. This post shows you how to migrate the adjacency list to a graph of one node and one edge. This is a continuation of what was started in this prior post.

In the Employees table, the employee’s manager has an EmployeeID which is stored in the employee’s ReportsTo column. A foreign key relationship is defined where the ReportsTo value stores the primary key of the row containing the manager’s data. For the highest level manager, the ReportsTo column is NULL. The relationship can be queried using a self-join.

image

Figure 1. Employee to Manager hierarchy implemented in the Northwind database.

The hierarchy can be displayed using a self-join.

SELECT e.FirstName, e.LastName, m.FirstName AS ManagerFirstName, m.LastName AS ManagerLastName
FROM dbo.Employees AS e
INNER JOIN dbo.Employees AS m
ON e.ReportsTo = m.EmployeeID;

FirstName LastName  ManagerFirstname ManagerLastName
--------- --------- ---------------- ---------------
Nancy     Davolio   Andrew           Fuller
Janet     Leverling Andrew           Fuller
Margaret  Peacock   Andrew           Fuller
Steven    Buchanan  Andrew           Fuller
Michael   Suyama    Steven           Buchanan
Robert    King      Steven           Buchanan
Laura     Callahan  Andrew           Fuller
Anne      Dodsworth Steven           Buchanan

To implement the hierarchy using a node and an edge, run the following code:

CREATE TABLE dbo.reportsTo AS EDGE;

INSERT INTO reportsTo
SELECT e.$node_id, m.$node_id
FROM dbo.EmployeesNode e
INNER JOIN dbo.EmployeesNode m
ON e.ReportsTo = m.EmployeeID;

To retrieve the employees and their managers, run the following query:

SELECT e.FirstName, e.LastName, m.FirstName AS ManagerFirstName, m.LastName AS ManagerLastName
FROM EmployeesNode AS e, reportsTo, EmployeesNode AS m
WHERE MATCH (e-(reportsTo)->m);

FirstName LastName  ManagerFirstname ManagerLastName
--------- --------- ---------------- ---------------
Nancy     Davolio   Andrew           Fuller
Janet     Leverling Andrew           Fuller
Margaret  Peacock   Andrew           Fuller
Steven    Buchanan  Andrew           Fuller
Michael   Suyama    Steven           Buchanan
Robert    King      Steven           Buchanan
Laura     Callahan  Andrew           Fuller
Anne      Dodsworth Steven           Buchanan

Astute observers will notice that something is missing from these queries. Before giving the answer away, look at the following query:

;WITH CTE (EmployeeID, EmployeeFirstName, EmployeeLastName, ManagerFirstName, ManagerLastName)
AS
(
-- anchor query
    SELECT e.EmployeeID, e.FirstName, e.LastName, CAST(NULL        AS NVARCHAR(20)), CAST(NULL       AS NVARCHAR(10))
    FROM dbo.Employees AS e
    WHERE e.ReportsTo IS NULL
    UNION ALL
-- recursive query
    SELECT e.EmployeeID, e.FirstName, e.LastName, CAST(m.FirstName AS NVARCHAR(20)), CAST(m.LastName AS NVARCHAR(10))
    FROM dbo.Employees AS e
    INNER JOIN dbo.Employees AS m
    ON e.ReportsTo = m.EmployeeID
    INNER JOIN CTE
    ON e.ReportsTo = CTE.EmployeeID
)
SELECT EmployeeFirstName, EmployeeLastName, ManagerFirstName, ManagerLastName
FROM CTE;

EmployeeFirstName EmployeeLastName ManagerFirstName ManagerLastName
----------------- ---------------- ---------------- ---------------
Andrew            Fuller           NULL             NULL
Nancy             Davolio          Andrew           Fuller
Janet             Leverling        Andrew           Fuller
Margaret          Peacock          Andrew           Fuller
Steven            Buchanan         Andrew           Fuller
Laura             Callahan         Andrew           Fuller
Michael           Suyama           Steven           Buchanan
Robert            King             Steven           Buchanan
Anne              Dodsworth        Steven           Buchanan

As you can see, special handling is required for handling the top of the hierarchy. A foreign key column in a relational table can allow NULL.

      NOTE: The CASTs were necessary to prevent the following error which has nothing to do with the subject of this post:

    Msg 240, Level 16, State 1, Line 1
    Types don't match between the anchor and the recursive part in column "ManagerFirstName" of recursive query "CTE".

What about an edge? Can it handle a NULL?

INSERT INTO reportsTo
SELECT e.$node_id, NULL
FROM dbo.EmployeesNode e
WHERE e.ReportsTo IS NULL;

Msg 515, Level 16, State 2, Line 70
Cannot insert the value NULL into column 'to_obj_id_762C07225C8943A99CF4494DFF96B4EE', table 'Northwind.dbo.reportsTo'; column does not allow nulls. INSERT fails.

The statement has been terminated.

I propose an approach similar to the common table expression query shown above.

SELECT FirstName, LastName, NULL AS ManagerFirstName, NULL AS ManagerLastName
FROM EmployeesNode
WHERE ReportsTo IS NULL
UNION ALL
SELECT e.FirstName, e.LastName, m.FirstName AS ManagerFirstName, m.LastName AS ManagerLastName
FROM EmployeesNode AS e, reportsTo, EmployeesNode AS m
WHERE MATCH (e-(reportsTo)->m);

FirstName LastName  ManagerFirstName ManagerLastName
--------- --------- ---------------- ---------------
Andrew    Fuller    NULL             NULL
Nancy     Davolio   Andrew           Fuller
Janet     Leverling Andrew           Fuller
Margaret  Peacock   Andrew           Fuller
Steven    Buchanan  Andrew           Fuller
Michael   Suyama    Steven           Buchanan
Robert    King      Steven           Buchanan
Laura     Callahan  Andrew           Fuller
Anne      Dodsworth Steven           Buchanan

I have another solution, but it is for another day.

Published Tuesday, June 20, 2017 9:53 PM by John Paul Cook

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

No Comments

Leave a Comment

(required) 
(required) 
Submit

About John Paul Cook

John Paul Cook is a database and Azure specialist in Houston. He previously worked as a Data Platform Solution Architect in Microsoft's Houston office. Prior to joining Microsoft, he was a SQL Server MVP. He is experienced in SQL Server and Oracle database application design, development, and implementation. He has spoken at many conferences including Microsoft TechEd and the SQL PASS Summit. He has worked in oil and gas, financial, manufacturing, and healthcare industries. John is also a Registered Nurse currently studying to be a psychiatric nurse practitioner. Contributing author to SQL Server MVP Deep Dives and SQL Server MVP Deep Dives Volume 2. Connect on LinkedIn

This Blog

Syndication

Privacy Statement