CTE for parent child relation with multiple parent

common-table-expression, graph, sql, sql-server-2005, t-sql

Solution

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

Problem

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

Original source