SQL Server 2012 CTE Find Root or Top Parent of Hierarchical Data

Question

I'm having an issue trying to recursively walk a hierarchy to find the top node of all descendent nodes in an organizational structure that may have multiple top-level nodes. I'm trying to use a SQL Server 2012 CTE to do so, but it won't recurse to reach the very top node of each branch. I've tried writing my query EXACTLY as shown in other posts relating to this, but still no dice. (At least I think I am.) I'm hoping someone can tell me what I'm doing wrong here? This post most closely relates to what I'm trying to do and I've followed the accepted answers, but I'm still just not "getting it" : Finding a Top Level Parent in SQL

As shown above, I have OrgGroups that reference direct parent groups, unless it's a top level and then it's NULL. For instance, (4) Finance (top-level) -> (5) HR -> (11) Benefits

I want to create a database view that lists each OrgGroup along with the ID of their TOP-MOST ancestor. (not their direct parent)

So, for example, the DB View would have a record for the (11) Benefits OrgGroup and a corresponding column value for it's top-most parentgroupId of (4) Finance.

;WITH OrgStructureIndex AS
(
   SELECT O.OrgGroupId, O.Name, O.OrgStructureId, O.ParentGroupId, 1 AS Lvl
   FROM OrgGroups O

   UNION ALL

   SELECT OG.OrgGroupId, OG.Name, OG.OrgStructureId, OG.ParentGroupId, Lvl+1 AS Lvl 
   FROM OrgGroups OG INNER JOIN OrgStructureIndex OI
    ON OI.OrgGroupId = OG.ParentGroupId
)

SELECT * FROM OrgStructureIndex

This results in the Benefits org group having a top-most ParentGroupId of (5) HR. Desired results would be (4) Finance. It also results in duplicate records.

To get rid of the duplicates at least, I've changed my SQL to:

;WITH OrgStructureIndex AS
(
  SELECT O.OrgGroupId, O.Name, O.OrgStructureId, O.ParentGroupId, 1 AS Lvl
  FROM OrgGroups O

  UNION ALL

  SELECT OG.OrgGroupId, OG.Name, OG.OrgStructureId, OG.ParentGroupId, Lvl+1 AS Lvl 
  FROM OrgGroups OG INNER JOIN OrgStructureIndex OI
    ON OI.OrgGroupId = OG.ParentGroupId
)
,CTE_RN AS 
(
  SELECT *, ROW_NUMBER() OVER (PARTITION BY oi.OrgGroupId ORDER BY oi.Lvl DESC) RN
  FROM OrgStructureIndex oi
)

SELECT * FROM CTE_RN
WHERE RN = 1

Where am I falling short here?? TIA

Answer 1

Two shortcomings:

• First, for some reason you decided to select all nodes in the anchor part of the CTE, not just the root ones. That's why you have a lot of duplicates.
• Second, you don't pass along the only field you actually need - the Id of the actual root.

Here is how you can fix them:

;WITH OrgStructureIndex AS
(
    SELECT O.OrgGroupId, O.Name, O.OrgStructureId, O.ParentGroupId, 1 AS Lvl,
        -- #2
        o.OrgGroupId as [RootGroupId]
    FROM OrgGroups O
    -- #1
    where o.ParentGroupId is null
    UNION ALL
    SELECT OG.OrgGroupId, OG.Name, OG.OrgStructureId, OG.ParentGroupId, Lvl+1 AS Lvl,
        -- #2
        oi.RootGroupId
    FROM OrgGroups OG INNER JOIN OrgStructureIndex OI
    ON OI.OrgGroupId = OG.ParentGroupId
)
SELECT * FROM OrgStructureIndex;

Answer 2

You can indeed walk up from the leaf node--as you are doing--to find the root of each original row. The thing your missing is tracking the starting leaf as you recurse up. Stripped down example:

fiddle

CREATE TABLE OrgGroup (OrgGroupId INT, Name VARCHAR(10), ParentGroupId INT)
GO

INSERT INTO OrgGroup VALUES 
(1,'Main', NULL),
(2,'IT',1),
(3,'DotCom',2),
(4,'Finance', NULL),
(5,'HR',4),
(6,'Accounting',4)

GO

;WITH cte AS
(
   SELECT 1 AS Lvl
         ,OrgGroupId LeafId
         ,OrgGroupId
         ,ParentGroupId
         ,Name
         ,Name LeafName

    FROM OrgGroup

   UNION ALL



   SELECT Lvl+1 AS Lvl 
         ,OI.LeafId
         ,OG.OrgGroupId
         ,OG.ParentGroupId
         ,OG.Name
         ,OI.LeafName
     FROM OrgGroup OG 
          INNER JOIN  
          cte OI ON OI.ParentGroupId = OG.OrgGroupId
)
,cte_rn AS (
SELECT * 
      ,ROW_NUMBER() OVER (PARTITION BY LeafID ORDER BY Lvl DESC) rn
  FROM cte
)
SELECT * FROM cte_rn WHERE rn = 1*