CODEWITHSUNDEEP
sqlsql-server-2008t-sqlcommon-table-expression
Peter Majeed
Peter Majeed

Reputation: 5352

(Reverse) Recursive Query

We have a role inheritance structure where instead of the highest level filtering down, it assumes that everyone by default gets the lowest level role, graphically depicted as follows:

role.Everyone //lowest level; everyone gets this role
  role.Applications // everyone assigned this role gets applications && everyone roles
    role.Databases // everyone assigned this role gets databases && applications && everyone roles
    role.SoftwareSubscriber
  role.Client_All // etc.
    role.Client
    role.ITClient
  role.Client
    role.NewsService // everyone assigned this role gets NewsService && Client && Everyone
                     // && Client_All roles, since Client is also a child of Client_All
    role.ClientDeliverable // etc.
  role.Employee
    role.Corporate
    role.Marketing
  role...
  ...

I would to retrieve all the "parents" (really, the children, but whatever) and their recursive parents of any given role. For instance, I'd expect a query that asks for the parents of role.Databases to return role.Applications and role.Everyone. Similarly, I'd expect a query that asks for the parents of role.NewsService to return role.Client, role.Everyone, and role.Client_All, since role.Client is a child of both role.Everyone and role.Client_All.

I tried to model a query as follows after MSDN's CTE example, but I'm at a loss in getting all of the recursive parents. Can anyone steer my CTE query in the right direction?

CREATE TABLE #ATTRIBASSIGN
(
    ATTRIBID int not null
    , ITEMID int not null
    , ITEMCLASS VARCHAR(10) NOT NULL DEFAULT ('ATTRIB')
    , CONSTRAINT PK_ATTRIBASSIGN_ATTRIBID_ITEMID_ITEMCLASS PRIMARY KEY (ATTRIBID, ITEMID, ITEMCLASS)
)

CREATE TABLE #ATTRIBPROP
(
    ATTRIBID int not null identity(1,1) primary key
    , ATTRIBNAME VARCHAR(50) not null 
)
GO

INSERT INTO #ATTRIBPROP (ATTRIBNAME)
VALUES ('role.Databases'), ('role.Applications'), ('role.Everyone'), ('role.Client_All'), ('role.Employee'), ('role.SoftwareSubscriber'),
    ('role.Client'), ('role.ITClient'), ('role.NewsService'), ('role.ClientDeliverable'), ('role.Corporate'), ('role.Marketing')

GO
INSERT INTO #ATTRIBASSIGN (ATTRIBID, ITEMID)
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Everyone'
    AND B.ATTRIBNAME = 'role.Applications'
UNION   
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Everyone'
    AND B.ATTRIBNAME = 'role.Client_All'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Everyone'
    AND B.ATTRIBNAME = 'role.Client'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Everyone'
    AND B.ATTRIBNAME = 'role.Employee'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Applications'
    AND B.ATTRIBNAME = 'role.Databases'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Applications'
    AND B.ATTRIBNAME = 'role.SoftwareSubscriber'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Client_All'
    AND B.ATTRIBNAME = 'role.Client'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Client_All'
    AND B.ATTRIBNAME = 'role.ITClient'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Client'
    AND B.ATTRIBNAME = 'role.NewsService'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Client'
    AND B.ATTRIBNAME = 'role.ClientDeliverable'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Employee'
    AND B.ATTRIBNAME = 'role.Corporate'
UNION
SELECT A.ATTRIBID, B.ATTRIBID
FROM #ATTRIBPROP A
    CROSS JOIN #ATTRIBPROP B
WHERE A.ATTRIBNAME = 'role.Employee'
    AND B.ATTRIBNAME = 'role.Marketing'

GO

WITH RoleStructure (parentRole, currentRole, Level)
AS
(
    SELECT B.ITEMID, B.ATTRIBID, 0 level
    FROM #ATTRIBASSIGN B 
    WHERE B.ATTRIBID NOT IN
        (
            SELECT ITEMID
            FROM #ATTRIBASSIGN C
            WHERE B.ATTRIBID = C.ITEMID
        )
        AND B.ITEMCLASS = 'attrib'
    UNION ALL
    SELECT B.ITEMID, B.ATTRIBID, D.level - 1
    FROM #ATTRIBASSIGN B 
        INNER JOIN RoleStructure D ON B.ATTRIBID = D.parentRole
    WHERE B.ITEMCLASS = 'attrib'
)
SELECT B.ATTRIBNAME, C.ATTRIBNAME, level
FROM RoleStructure A
    INNER JOIN #ATTRIBPROP B ON A.parentRole = B.ATTRIBID
    INNER JOIN #ATTRIBPROP C ON A.currentRole = C.ATTRIBID

Upvotes: 4

Views: 4209

Answers (1)

jklemmack
jklemmack

Reputation: 3636

Thanks for the comprehensive SQL and sample data - that made building the answer much much easier! Looks like your main mistake was confusing yourself between parent & child. I think you focused too much on how the structure is "in reverse" and out-reversed your thinking. I made two main edits to your SQL to make it work.

1) Flipped the parent & current items. In "AttribAssign", I treated ATTRIBID as the "parent" and "ITEMID" as the "child", so you have a nice regular tree. I also ended up flipping around the 2nd half of the UNION (the recursive part) to line up

2) I did NOT filter the 'anchor' set of data. The extra 10 rows were necessary to keep the recursion going like you wanted. I did this because you wanted to have one row of output for any parent/child combination, regardless of the level of recursion. Your original table has all "direct" combinations. You want to expand each and every "direct" to include N+1 levels of indirection. What your query gave was only the "direct" relationships. By keeping all the original links, we could build off of that set to better find all links regardless of the level of indirection. Confusing, yes, but it works.

;WITH RoleStructure (parentRole, currentRole, Level) 
AS 
( 
        SELECT B.ATTRIBID, B.ITEMID, 0 level 
        FROM #ATTRIBASSIGN B  
        WHERE B.ITEMCLASS = 'attrib' 

        UNION ALL 

        SELECT D.parentRole, B.ITEMID, D.level - 1 
        FROM #ATTRIBASSIGN B  
                INNER JOIN RoleStructure D ON B.ATTRIBID = D.currentRole
        WHERE B.ITEMCLASS = 'attrib' 
) 
SELECT a.parentRole, a.currentRole, B.ATTRIBNAME, C.ATTRIBNAME, level 
FROM RoleStructure A 
        INNER JOIN #ATTRIBPROP B ON A.parentRole = B.ATTRIBID 
        INNER JOIN #ATTRIBPROP C ON A.currentRole = C.ATTRIBID

Upvotes: 6

Related Questions