Traversing a Recursive Table Self Reference Using T-SQL

Randy Evans here…I am a Principal Architect on the Information Security Tools team.  During the Risk Tracker project (something well be talking more about in the coming weeks), we found that a natural hierarchy of roles was inherent in the RBA authorization design.  For example, the “Task User” role has a set of permissions and the “Task Manager” role requires all the same permissions of a “Task User” plus some additional permissions.  The “Risk Manager” role requires all the same permissions of a “Task Manager” plus some additional permissions and so on.  To model this hierarchy we added a recursive table self reference to the Role table by adding a ParentRoleID column.

 CREATE TABLE [dbo].[Role](
[RoleID] [int] IDENTITY(1,1) NOT NULL,
[RoleName] [nvarchar](50) NOT NULL,
[ParentRoleID] [int] NULL)

Traversing a recursive table self reference can be a little confusing to code using T-SQL; especially if you don’t have a defined number of recursions.  Below is the approach we used to find all descendants of any particular role using T-SQL.  The first “insert into” primes the temp table by finding all child roles with a ParentRoleID matching the top level role that we’re interested in.  The second “insert into” populates the temp table with all remaining descendants by looping until no more records are selected.  The second query looks for all children with ParentRoleIDs that match any RoleID in the temp table.  It uses a correlated subquery to prevent previously selected roles from being selected again.  The final query simply returns all roles found in the temp table.  This pattern will work regardless of the number of levels that exist in the role hierarchy.

 DELCARE @role as nvarchar(50) = 'Risk Manager'
     
CREATE TABLE [dbo].[#TopRoles] (RoleID int, ParentRoleID int)

/*Get the immediate children of the passed in role. */ 

 INSERT INTO [dbo].[#TopRoles]
SELECT child.RoleID
, child.ParentRoleID
FROM [dbo].[Role] parent
JOIN [dbo].[Role] child
ON   child.ParentRoleID = parent.RoleID
AND  parent.RoleName = @role

WHILE @@ROWCOUNT > 0
BEGIN

/*Get the children's children. */ 

     INSERT INTO [dbo].[#TopRoles]
   SELECT child.RoleID
 , child.ParentRoleID
    FROM [dbo].[#TopRoles] parent
   JOIN [dbo].[Role] child
 ON   child.ParentRoleID = parent.RoleID  --Gets the children
    AND  not exists (           --Don't return rows that already exist.
 SELECT parent2.RoleID 
  FROM [dbo].[#TopRoles] parent2
  WHERE parent2.RoleID = child.RoleID)
END

SELECT 
r.RoleName
FROM [dbo].[#TopRoles] tr
JOIN [dbo].[Role] r
ON   r.RoleID = tr.RoleID

Hope you find this useful if you are faced solving similar problems!