Recursive Relationship Query

Question

I am looking to implement graph tables to map the role hierarchy for my application in Azure SQL. The graph will look like a tree if it is laid out. With the parent being able to manage any role that falls beneath it on the tree.

So I have a roles node table and a canmanage edge table.

I am familiar with querying the first level and the second level of relationships, however I need to have a query where I can put in any role and receive a list of all the children that fall under it.

I am familiar with this sort of thing in NEO4J, but I have not found any documentation on how to accomplish this in Azure SQL.

How do I go about running a recursive query to get all the child roles give a specific role name or id?

Answer 1

This is possible from SQL Server 2017 and Azure SQL DB using the new graph database capabilities and the new MATCH clause to model this type of relationship. Unfortunately in v1 polymorphism and transitive closure are not natively included but are possible using recursive queries. If you look at the last query, it keep the parameter you input as the top-level manager and iterates over the rest.

A sample script:

USE tempdb
GO

-- NODES
DROP TABLE IF EXISTS dbo.roles

-- EDGES
DROP TABLE IF EXISTS dbo.canManage
DROP TABLE IF EXISTS dbo.isManagedBy
GO

CREATE TABLE dbo.roles (
    roleId      INT PRIMARY KEY,
    roleName    VARCHAR(20) UNIQUE NOT NULL
    ) AS NODE

CREATE TABLE dbo.canManage AS EDGE;
CREATE TABLE dbo.isManagedBy AS EDGE;
GO


-- Populate node table
INSERT INTO dbo.roles ( roleId, roleName )
VALUES
    ( 1, 'CEO' ),
    ( 2, 'VP 1' ),
    ( 3, 'VP 2' ),
    ( 4, 'Sales Manager 1' ),
    ( 5, 'Sales Manager 2' ),
    ( 6, 'Ops Manager 1' ),
    ( 7, 'Ops Manager 2' ),
    ( 8, 'Sales Lead 1' ),
    ( 9, 'Salesperson 1' ),
    ( 10, 'Salesperson 2' ),
    ( 11, 'Salesperson 3' )
GO


-- Populate edge table
INSERT INTO dbo.canManage ( $from_id, $to_id )
SELECT ceo.$node_id, VPs.$node_id
FROM dbo.roles ceo
    CROSS JOIN dbo.roles VPs
WHERE ceo.roleName = 'CEO'
  AND VPs.roleName Like 'VP%'


-- VP 1 manages Sales Managers
INSERT INTO dbo.canManage ( $from_id, $to_id )
SELECT a.$node_id, b.$node_id
FROM dbo.roles a
    CROSS JOIN dbo.roles b
WHERE a.roleName = 'VP 1'
  AND b.roleName Like 'Sales Manager%'


-- VP 2 manages Ops Managers
INSERT INTO dbo.canManage ( $from_id, $to_id )
SELECT a.$node_id, b.$node_id
FROM dbo.roles a
    CROSS JOIN dbo.roles b
WHERE a.roleName = 'VP 2'
  AND b.roleName Like 'Ops Manager%'


-- Sales Manger 1 manages Sales Leads
INSERT INTO dbo.canManage ( $from_id, $to_id )
SELECT a.$node_id, b.$node_id
FROM dbo.roles a
    CROSS JOIN dbo.roles b
WHERE a.roleName = 'Sales Manager 1'
  AND b.roleName Like 'Sales Lead%'


-- Sales Leads 1 manages all salespersons
INSERT INTO dbo.canManage ( $from_id, $to_id )
SELECT a.$node_id, b.$node_id
FROM dbo.roles a
    CROSS JOIN dbo.roles b
WHERE a.roleName = 'Sales Lead 1'
  AND b.roleName Like 'Salesperson%'


-- Create the inverse edge / relationship
INSERT INTO dbo.isManagedBy ( $from_id, $to_id )
SELECT $to_id, $from_id
FROM dbo.canManage 
GO



-- Now write the graph queries:

-- Manages
SELECT FORMATMESSAGE( '%s manages %s', r1.roleName, r2.roleName ) manages
FROM dbo.roles r1, dbo.canManage canManage, dbo.roles r2
WHERE MATCH ( r1-(canManage)->r2 )


-- Same manager
SELECT FORMATMESSAGE( '%s and %s have the same manager %s', r1.roleName, r3.roleName, r2.roleName )
FROM dbo.roles r1, dbo.isManagedBy m1, dbo.roles r2, dbo.isManagedBy m2, dbo.roles r3
WHERE MATCH ( r1-(m1)->r2<-(m2)-r3 )
AND r1.$node_id < r3.$node_id



-- Recursive
-- walk the tree ... CEO manages everyone ...
;WITH cte AS (
SELECT 1 xlevel, r1.roleName manager, r2.roleName managed
FROM dbo.roles r1, dbo.canManage canManage, dbo.roles r2
WHERE MATCH ( r1-(canManage)->r2 )
AND r1.roleName = 'CEO'

UNION ALL

SELECT c.xlevel + 1, r1.roleName, r2.roleName
FROM cte c, dbo.roles r1, dbo.canManage canManage, dbo.roles r2
WHERE c.managed = r1.roleName
  AND MATCH ( r1-(canManage)->r2 )
)
SELECT *
FROM cte
ORDER BY xlevel, manager, managed



;WITH cte AS (
SELECT 1 xlevel, r1.roleName manager, r2.roleName managed
FROM dbo.roles r1, dbo.canManage canManage, dbo.roles r2
WHERE MATCH ( r1-(canManage)->r2 )
AND r1.roleName = 'CEO'

UNION ALL

SELECT c.xlevel + 1, c.manager, r2.roleName
FROM cte c, dbo.roles r1, dbo.canManage canManage, dbo.roles r2
WHERE c.managed = r1.roleName
  AND MATCH ( r1-(canManage)->r2 )
)
SELECT *
FROM cte
ORDER BY xlevel, manager, managed