CODEWITHSUNDEEP
sqlsql-servert-sqlrecursive-queryancestor
Xristos Epitropakis
Xristos Epitropakis

Reputation: 13

Recursive sql - find the grandgrandparent of a child

I have a table like the below:

Id ParentID 1 99 2 9 3 1 4 2 5 4 6 3

and I would like to have a query that gives me for each child the last ancestor.

I mean that the desired result is

id Lastancestor 1 99 2 9 3 99 4 9 5 9 6 99

I have a lot of data so I need something quick.

Thanks.

Upvotes: 0

Views: 152

Answers (2)

Giorgos Betsos
Giorgos Betsos

Reputation: 72205

You can use a Recursive CTE to accomplish this:

;WITH CTE AS (
  SELECT Id AS origId, ParentID, 0 AS lvl
  FROM mytable

  UNION ALL

  SELECT c.origId AS origId, 
         m.ParentID, lvl = lvl + 1
  FROM CTE AS c
  INNER JOIN mytable AS m ON c.ParentID = m.Id
)
SELECT origId AS id, ParentID AS Lastancestor
FROM (
  SELECT origId, ParentID,
         ROW_NUMBER() OVER (PARTITION BY origId 
                            ORDER BY lvl DESC) AS rn
  FROM CTE) AS t
WHERE t.rn = 1

Here, the anchor member of the CTE is just the whole table. Recursion goes up the tree hierarchy while propagating the original Id (as origId) down the recursion chain. The recursion terminates as soon as an empty set is returned, i.e. as soon as no more c.ParentID = m.Id matches are found.

To get the required result, i.e. the Lastancestor per id, all we need to do is fetch the record having the greatest lvl (i.e. depth) per id. This is achieved using ROW_NUMBER window function.

Demo here

Upvotes: 2

Gottfried Lesigang
Gottfried Lesigang

Reputation: 67321

If there is a maximum depth you could use this approach. You can add further depth levels with simple copy and past and adapt. I added one data element "19,6" to generate one with three ancestors and one with four.

Just paste this into an empty query window and execute. Adapt to your needs...

declare @Test table (Id int, ParentID int)

insert into @Test values
(1,99)
,(2,9)
,(3,1)
,(4,2)
,(5,4)
,(6,3)
,(19,6);


WITH Ancestors1 AS
(
    SELECT Test.*
          ,Ancestor.ParentID AS Anc1ID 
    FROM @Test AS Test
    LEFT JOIN @Test AS Ancestor ON Test.ParentID=Ancestor.Id
)
,Ancestors2 AS
(
    SELECT Ancestors1.*
          , Ancestor.ParentID AS Anc2ID 
    FROM Ancestors1
    LEFT JOIN @Test AS Ancestor ON Ancestors1.Anc1ID=Ancestor.Id
)
,Ancestors3 AS
(
    SELECT Ancestors2.*
          , Ancestor.ParentID AS Anc3ID 
    FROM Ancestors2
    LEFT JOIN @Test AS Ancestor ON Ancestors2.Anc2ID=Ancestor.Id
)
SELECT Id,*
      ,COALESCE(Anc3ID,Anc2ID,Anc1ID,ParentID)  AS LastAncId
FROM Ancestors3

Upvotes: 0

Related Questions