SQL Server CTE -Find top parentID forEach childID?

Question

I have a table which contains hierarchy data - something like:

childID  |  parentID
____________________
  1      |     5
  5      |     9
  9      |     20
  2      |     4
  3      |     7
  7      |     8
  8      |     8
 20      |     20
  4      |     4
  8      |     8

desired output:

I've created a recursive CTE which finds me the top fatherID.

Something like:

;WITH cte AS (
                 SELECT a.childID
                       ,a.parentID
                       ,1 AS lvl
                 FROM   [Agent_Agents] a
                 WHERE   a.childID = 214 //<==== value to begin with !! - thats part the problem
                 UNION ALL
                 SELECT tmp.childID
                       ,tmp.parentID
                       ,cte.lvl+1
                 FROM   [Agent_Agents] tmp
                         INNER JOIN cte  ON  tmp.childID = cte.parentID
                 WHERE   cte.childID<>cte.parentID
             )
SELECT *
FROM   cte
WHERE   lvl = (
            SELECT MAX(lvl)
            FROM   cte
        )

The problem:

I executed the CTE with explicit childID value to begin with (214) ! So it gives me the value for 214 only. the CTE do the recursive part and find topParent for childID.

but I want ForEach row in the Table - to execute the CTE with the childID value !

I have tried to do it with CROSS APPLY:

Something like:

select * from myTable Cross Apply (
                                     ;WITH cte AS (....)
                                  )

but IMHO (from my testing !!) - its impossible.

The other idea of putting the recursive CTE in a UDF has a performance penalty (udf's problem as we know).

How can I create this query so that it'll actually work? ( or some near solution )?

here is what I've tried

https://data.stackexchange.com/stackoverflow/query/edit/69458

Solution 1

Not sure I understand what you are looking for but it could be this.

;WITH c 
     AS (SELECT childid, 
                parentid, 
                parentid AS topParentID 
         FROM   @myTable 
         WHERE  childid = parentid 
         UNION ALL 
         SELECT T.childid, 
                T.parentid, 
                c.topparentid 
         FROM   @myTable AS T 
                INNER JOIN c 
                        ON T.parentid = c.childid 
         WHERE  T.childid <> T.parentid) 
SELECT childid, 
       topparentid 
FROM   c 
ORDER  BY childid 

SE-Data

It is the same as answer by marc_s with the difference that I use your table variable and the fact that you have childID = parentID for root nodes where the answer by marc_s has parent_ID = null for root nodes. In my opinion it is better to have parent_ID = null for root nodes.

Solution 2

Can't you do something like this?

;WITH cte AS (....)
SELECT
    * 
FROM 
    cte
CROSS APPLY 
    dbo.myTable tbl ON cte.XXX = tbl.XXX

Put the CROSS APPLY after the CTE definition - into the one SQL statement that refers back to the CTE. Wouldn't that work??

OR: - flip around your logic - do a "top-down" CTE, that picks the top-level nodes first, and then iterates through the hiearchy. This way, you can easily determine the "top-level father" in the first part of the recursive CTE - something like this:

;WITH ChildParent AS
(
    SELECT
        ID,
        ParentID = ISNULL(ParentID, -1),
        SomeName, 
        PLevel = 1,   -- defines level, 1 = TOP, 2 = immediate child nodes etc.
        TopLevelFather = ID  -- define "top-level" parent node
    FROM dbo.[Agent_Agents] 
    WHERE ParentID IS NULL

    UNION ALL

    SELECT
        a.ID,
        ParentID = ISNULL(a.ParentID, -1),
        a.SomeName, 
        PLevel = cp.PLevel + 1,
        cp.TopLevelFather   -- keep selecting the same value for all child nodes
    FROM dbo.[Agent_Agents] a
    INNER JOIN ChildParent cp ON r.ParentID = cp.ID
)
SELECT  
   ID,
   ParentID,
   SomeName,
   PLevel,
   TopLevelFather   
FROM ChildParent

This would give you nodes something like this (based on your sample data, slightly extended):

ID  ParentID  SomeName      PLevel  TopLevelFather
20    -1      Top#20           1          20
 4    -1      TOP#4            1           4
 8    -1      TOP#8            1           8
 7     8      ChildID = 7      2           8
 3     7      ChildID = 3      3           8
 2     4      ChildID = 2      2           4
 9    20      ChildID = 9      2          20
 5     9      ChildID = 5      3          20
 1     5      ChildID = 1      4          20

Now if you select a particular child node from this CTE output, you'll always get all the infos you need - including the "level" of the child, and its top-level parent node.

Solution 3

I have not yet the time to look further into your question and am not sure whether or not i've understood your problem, but couldn't you use this svf to get the top father's id?

CREATE FUNCTION [dbo].[getTopParent] (
    @ChildID INT
)

RETURNS int
AS
BEGIN
    DECLARE @result int;
    DECLARE @ParentID int;

    SET @ParentID=(
        SELECT ParentID FROM ChildParent
        WHERE ChildID = @ChildID 
    )

    IF(@ParentID IS NULL)
        SET @result = @ChildID 
    ELSE
        SET @result = [dbo].[getTopParent](@ParentID)

    RETURN @result    
END

Then you should be able to find each top parent in this way:

SELECT ChildID
    ,  [dbo].[getTopParent](ChildID) AS TopParentID
FROM ChildParent

Comments

[Royi Namir]

I dont think it will wiork - since CTE knows how to execute and find one(!!) top father for ID. notice the 214 value..... how will i send Foreach ID => Cte.DoWorkFor(ID) ?

[marc_s]

@RoyiNamir: with this ChildParent CTE - can't you just do SELECT * FROM ChildParent WHERE ID = 214 and get what you need??

[Royi Namir]

Thanks for answering. tim. the problem ( as we know ) tha t udf reduces performance ( while inline calling...) thats why i tend to avoid this kind of solution. the problem ( in general) : i have table with id and parentId. foreach line in the (select * from ...) - i need another column which has the topmost father value.- ive tried with Cross Aply - vut the recursive engine ( CTE) cant be used with Cross Apply).

[Royi Namir]

ive added a print screen to the desired output.

[Royi Namir]

ive added a print screen for the desired output.

[Mikael Eriksson]

@RoyiNamir - My query on SE-Data returns what you want. I just added the name and parentID columns.

[Royi Namir]

Ill be GLAD to hear why you decided to start with the topmost - and not the leafs .... what is the logic here (although its working) ? why couldn't we start with the leafs towards topmost leafs ?

[Mikael Eriksson]

@RoyiNamir Going from the leaf node will add more rows to the result set than you need. If one parent has three children you will have that parent in the result set three times. Going from top to bottom in the recursive query you only add the new nodes you find one time for each node.

[Sled]

please explain your answer instead of just giving it

[Bharani]

I have using the without CTE expression and then using joins to get the step to step parent for child and then more important Common table expressions were introduced in SQL Server 2005 not in server 2000 so using joins to get values this is basic way for to get parentid for a child value

[Royi Namir]

you said : "If one parent has three children you will have that parent in the result set three times" - but accroding to my question - you should see it 3 times. no ?if 1 has parent 2 , and 5 has parent 2 , and 9 has parent 2 – you should see 1,2 & 5,2 & 9,2 .... no ?

[Mikael Eriksson]

@RoyiNamir I meant that you will have the parent three times in the result set like this if you get the leaf nods in the achor.

[Vladimir Baranov]

This solution doesn't answer the question. Original data doesn't have NULL in ParentID. The suggested query doesn't produce the desired output.