CTE for parent child relation with multiple parent

Question

I have a parent child relation table as shown below. I want to retrieve all records for a parent or child ID like all ancestors and parents and if possible with depth. For example I want to find the family of D, it will return the first 14 rows as all are of same family. There may be several set of such family. I want to query with one member and want to get whole family record. Is it possible to implement this using CTE? The family structures as per table record :

                      A
                     / \
                    B   C   G   J
                   /     \ / \ / \
              M   D       E   H   K
             / \ /             \ / \
            N   F               I   L


                 R
                 |
                 S   U
                  \ /
                   T

Please help. The table is like:

   Parent   Child
    ------  ------
    A            B
    A            C
    B            D
    D            F
    M            F
    M            N
    C            E
    G            E
    G            H
    J            H
    J            K
    H            I
    K            I
    K            L
    R            S
    S            T
    U            T

Thanks,

Himadri

Answer 1

This solution will only work with acyclic graphs as the recursion will break if it cycles, taking the data set as supplied...

create table nodes
(
    p char, 
    c char
)
insert into nodes (p, c)
values
    ('A', 'B'), ('A', 'C'), ('B', 'D'), ('D', 'F'), ('M', 'F'), ('M', 'N'), ('C', 'E'),
    ('G', 'E'), ('G', 'H'), ('J', 'H'), ('J', 'K'), ('H', 'I'), ('K', 'I'), ('K', 'L'),
    ('R', 'S'), ('S', 'T'), ('U', 'T')

GO

We can get the forward tree parent -> child by recursing over the original node records

CREATE VIEW dbo.Tree
AS
    WITH Hierarchy(r, p, c, [Level])
    AS 
    (
        SELECT p AS r,
               p,
               c,
               0 AS [Level]
        FROM dbo.nodes
        UNION ALL
        SELECT n.p AS r,
               t.p,
               t.c,
               t.[Level] + 1
        FROM Hierarchy t
        INNER JOIN dbo.nodes n ON n.c = t.r
        AND n.p != t.p
    )
    SELECT r, p, c, [Level]
    FROM Hierarchy

This then gives the result

r   p   c   Level
A   A   B   0
A   A   C   0
A   C   E   1
A   D   F   2
A   B   D   1
B   D   F   1
B   B   D   0
C   C   E   0
D   D   F   0
G   G   E   0
G   G   H   0
G   H   I   1
H   H   I   0
J   H   I   1
J   K   L   1
J   K   I   1
J   J   H   0
J   J   K   0
K   K   I   0
K   K   L   0
M   M   F   0
M   M   N   0
R   R   S   0
R   S   T   1
S   S   T   0
U   U   T   0

We can then do this the other way so we can walk from a child up through to its parent(s)

CREATE VIEW dbo.ReverseTree
AS
    WITH Hierarchy(r, c, p, [Level])
    AS 
    (
        SELECT c AS r,
               c,
               p,
               0 AS [Level]
        FROM dbo.nodes
        UNION ALL
        SELECT n.c AS r,
               t.c,
               t.p,
               t.[Level] + 1
        FROM Hierarchy t
        INNER JOIN dbo.nodes n ON n.p = t.r
        AND n.c != t.c
    )
    SELECT r, c, p, [Level]
    FROM Hierarchy

And the results from that look like this

r   c   p   Level
B   B   A   0
C   C   A   0
D   D   B   0
D   B   A   1
E   C   A   1
E   E   C   0
E   E   G   0
F   F   D   0
F   F   M   0
F   D   B   1
F   B   A   2
H   H   G   0
H   H   J   0
I   I   H   0
I   I   K   0
I   K   J   1
I   H   J   1
I   H   G   1
K   K   J   0
L   K   J   1
L   L   K   0
N   N   M   0
S   S   R   0
T   T   S   0
T   T   U   0
T   S   R   1

This is handy for things like breadcrumb trails

Answer 2

I will post my solution with a string limiter of the recursion. I wondered if it is good to do it this way performance wise for a big graph, but i think it's not so bad after all. Basically i'm processing the relations recursively, recording the "path" that got me to each step, and checking the path so that i can stop when i hit a circular relation.

For anyone who wants to try it, i'm posting the create and filling of the table:

create table nodes
(
    p char, 
    c char
)
insert into nodes (p, c)
values
    ('A', 'B'), ('A', 'C'), ('B', 'D'), ('D', 'F'), ('M', 'F'), ('M', 'N'), ('C', 'E'),
    ('G', 'E'), ('G', 'H'), ('J', 'H'), ('J', 'K'), ('H', 'I'), ('K', 'I'), ('K', 'L'),
    ('R', 'S'), ('S', 'T'), ('U', 'T')

And here is the query:

declare @let char = 'D';
with cte as
(
    --get the node itself if it exists in the table at all
    select 
        top 1 @let as letter, '' as rec_path 
    from 
        nodes 
    where 
        c = @let or p = @let 

    union all
    -- get the direct relations of the node as a starting point
    select 
        case when c = @let then p else c end as letter, 
        cast(@let as varchar(max)) as rec_path
    from 
        nodes 
    where 
        c = @let or p = @let

    union all
    -- get all of the relations recursively until you reach a node you already processed
    select 
        case when c = cte.letter then p else c end as letter, 
        rec_path + cte.letter as rec_path
    from 
        cte
        join nodes on 
            (cte.letter = nodes.c and charindex(cast(nodes.p as varchar(1)), rec_path, 1) = 0 
            or (cte.letter = nodes.p and charindex(cast(nodes.c as varchar(1)), rec_path, 1) = 0))
)
select 
    distinct letter
from 
    cte

I hope it will be useful. I realize that your data does not actually consist of letters, but the same can be done with id-s using again a string path, or even a xml.

Answer 3

I found a solution. But I used CTE in a while loop. If someone has any other solution please suggest. As I have mentioned a table above that contains family records or you can say graphs. Let's name it as tbl_ParentChild.

Here is my code:

Declare @Child varchar(10), @RowsEffected int
Set @Child='D'-----It is the member whose family we want to find

 CREATE Table #PrntChld (Parent varchar(10),Child varchar(10))
 Insert Into #PrntChld
 Select Parent,Child  from tbl_ParentChild MF
 Where MF.Child=@Child or MF.Parent=@Child

 Select @RowsEffected=Count(*) from #PrntChld

 While @RowsEffected>0 
 BEGIN
    ;WITH Prnt(Parent,Child)
        AS
        ( Select M.Parent,M.Child  from tbl_ParentChild M
            Inner Join #PrntChld F On F.Child=M.Child
          UNION ALL
          SELECT e.Parent,e.Child       
              FROM tbl_ParentChild AS E
              INNER JOIN  Prnt AS M                 
                  ON E.Child = M.Parent           
        ),
        PrntChld(Parent,Child)
        AS
        ( Select M.Parent,M.Child  from tbl_ParentChild M
            Inner Join (Select * from Prnt union Select * from #PrntChld) F On M.Parent=F.Parent
          UNION ALL
          SELECT e.Parent,e.Child       
              FROM tbl_ParentChild AS E
              INNER JOIN  PrntChld AS M                 
                  ON M.Child = E.Parent           
        )

    Insert Into #PrntChld
    Select distinct MF.* from PrntChld MF 
    Left Join #PrntChld T On T.Child =MF.Child and T.Parent  = MF.Parent    
    where T.Child is null
    Select @RowsEffected=@@ROWCOUNT

END

Select * from #PrntChld
drop table #PrntChld