Parent Child SQL Recursion

Question

I have seen similar but not Exactly the same requests.

If I had the following table

Parent  Child
1       2
1       3
4       3
5       1
6       1
5       7
8       9

I selected "1" I would expect back all records where one is the parent or child but also all related parents and children for instance row "5 , 7" because 5 is the parent of "1"

so the result set for 1 would be

Parent  Child
1       2
1       3
4       3
5       1
6       1
5       7

So it would NOT include the row

Parent  Child
8       9

This is as close as I can get so far

;WITH LinksDown AS (
   SELECT *
   FROM RecursiveTable
   WHERE Parent = 1
   UNION ALL
   SELECT rt.*
   FROM RecursiveTable rt
   JOIN LinksDown ld on ld.Child = rt.Parent
),

LinksUp AS (
   SELECT *
   FROM RecursiveTable
   WHERE Child = 1
   UNION ALL
   SELECT rt.*
   FROM RecursiveTable rt
   JOIN LinksUp lu on lu.Child = rt.Parent
) 

select distinct *
from LinksDown

Union All 
select distinct * from LinksUp

But this has the following output which is far from whats needed

Parent  Child
1       2
1       3
1       2
1       3
5       1
6       1

Solution 1

Here are two approaches. The first uses a CTE that is quite inefficient. The problem is that during recursion you cannot examine all of the other rows in the result set. While you can build a list of the rows that have contributed to a given row, you cannot check to see if you already reached that row via another path. The second approach uses a loop to populate a table with relations one step at a time. It is a much better method than the CTE.

Left as an exercise for the reader: Will the two methods terminate in the presence of a cycle in the "tree", e.g. 1 > 2 > 3 > 1?

-- Sample data.
declare @RecursiveTable as Table ( Parent Int, Child Int );
insert into @RecursiveTable ( Parent, Child ) values
  ( 1, 2 ), ( 1, 3 ),
  ( 4, 3 ),
  ( 5, 1 ),
  ( 6, 1 ),
  ( 5, 7 ),
  ( 8, 9 );
select * from @RecursiveTable;

-- Walk the tree with a recursive CTE.
--   NB: This is woefully inefficient since we cannot promptly detect
--   rows that have already been processed.
declare @Start as Int = 1;
with Pairs as (
  select Parent, Child, Cast( Parent as VarChar(10) ) + '/' + Cast( Child as VarChar(10) ) as Pair
    from @RecursiveTable ),
 Relations as (
  select Parent, Child, Cast( '|' + Pair + '|' as VarChar(1024) ) as Path
    from Pairs
    where Parent = @Start or Child = @Start
  union all
  select P.Parent, P.Child, Cast( R.Path + P.Pair + '|' as VarChar(1024) )
    from Relations as R inner join
      Pairs as P on P.Child = R.Parent or P.Parent = R.Child or
        P.Child = R.Child or P.Parent = R.Parent
    where CharIndex( '|' + P.Pair + '|', R.Path ) = 0
  )
  -- To see how terrible this is, try: select * from Relations
  select distinct Parent, Child
    from Relations
    order by Parent, Child;

-- Try again a loop to add relations to a working table.
declare @Relations as Table ( Parent Int, Child Int );
insert into @Relations
  select Parent, Child
    from @RecursiveTable
    where Parent = @Start or Child = @Start;
while @@RowCount > 0
  insert into @Relations
    select RT.Parent, RT.Child
      from @Relations as R inner join
        @RecursiveTable as RT on RT.Child = R.Child or RT.Parent = R.Parent or
          RT.Child = R.Parent or RT.Parent = R.Child
    except
    select Parent, Child
      from @Relations;
select Parent, Child
  from @Relations
  order by Parent, Child;

Solution 2

I think that you could still do this with a CTE, as part of a stored procedure. (The performance will be lousy, but this should work.)

The normal method of using recursive CTE's commonly generates 3 columns: ParentID, ChildID, RecursionLevel.

My suggestions is to return one more column... A string that is the concatenation of all of the parents IDs. (Probably with some separator value, like a vertical pipe.) From there, you should be able to select every row where the IDString column contains your ID. (In your case, it would be "1".) This should return every record where your search ID occurs somewhere within the hierarchy, and not just as a parent or child.

EDIT: Here is a sample. I'm using curly brackets { and } as my separators, I also realized that the code would be cleaner if I added an "IsLeaf" indicator to reduce duplication, since the leaf-level records would contain the IDs of all of their ancestors...

DECLARE @MyTable TABLE(P int, C int)  -- Parent & Child

INSERT @MyTable VALUES( 1, 2 );
INSERT @MyTable VALUES( 1, 3 );
INSERT @MyTable VALUES( 3, 4 );
INSERT @MyTable VALUES( 3, 5 );
INSERT @MyTable VALUES( 2, 6 );
INSERT @MyTable VALUES( 5, 7 );
INSERT @MyTable VALUES( 6, 8 );
INSERT @MyTable VALUES( 8, 9 );

-- In order to user a recursive CTE, you need to "know" which records are the 'root' records...
INSERT @MyTable VALUES ( null, 1 );

/*
        9
       /
      8
     /
    6
   / 
  2   
 /     
1   4    Using this example, if the user searched for 1, everything would show up.
 \ /       Searching for 3 would return 1, 3, 4, 5, 7
  3        Searching for 7 would return 1, 3, 5, 7
   \
    5
     \
      7
*/


WITH RecursiveCTE AS (
    SELECT C as ID, 
         0 as Level, 
         CONVERT(varchar(max), '{' + CONVERT(char(1), C) + '}') as IDList,
         CASE WHEN EXISTS (SELECT * FROM @MyTable B Where B.P = 1) THEN 0 ELSE 1 END as IsLeaf
    FROM @MyTable A
    Where A.P IS NULL
  UNION ALL
  SELECT child.C as ID, 
          Level + 1 as Level, 
          IDList + '{' + CONVERT(varchar(max), child.C) + '}' as IDList, 
          CASE WHEN EXISTS (SELECT * FROM @MyTable C Where C.P = child.C) THEN 0 ELSE 1 END as IsLeaf
    FROM RecursiveCTE as parent
    INNER JOIN @MyTable child ON child.P = parent.ID
)
SELECT IDList -- Every ID listed here is a row that you want.
FROM   RecursiveCTE 
WHERE  IsLeaf = 1
AND    IDList LIKE '%{3}%'

Solution 3

It's not efficient but it will do the job:

select * from pc;
declare @t table (cid int);
declare @r int;
insert into @t (cid)values(1); -- this is the "parent"
set @r=@@rowcount;
while @r>0 begin
    insert into @t 
    (cid) select pid from pc where (pid in (select cid from @t) or cid in (select cid from @t) ) and pid not in (select cid from @t)
    union select cid from pc where (pid in (select cid from @t) or cid in (select cid from @t) ) and pid not in (select cid from @t);
    set @r = @@ROWCOUNT;
end;

select * from pc where pid in (select cid from @t) or cid in (select cid from @t);

The table will be

1   2
1   3
4   3
5   1
6   1
5   7
8   9

The output will be :

1   2
1   3
5   1
6   1
5   7

Comments

[MicroMan]

Could you send an example?