Getting all descendants of a parent

Question

I have a table with two columns, Parent and Child.

I need to get the list of all descendants associated with the parent records.

Source Table
+----+-----------+
| Parent | Child |
+----+-----------+
|  a     |     b |
|  b     |     c |
|  c     |     d |
|  d     |     e |
|  e     |     f |
|  f     |     x |
+----+-----------+

Expected Result:
+----+-----------+
| Parent | Child |
+----+-----------+
|  a     |     b |  // As b is the child of a, all the descendants of b 
|  a     |     c |  // are also descendants of a. 
|  a     |     d |
|  a     |     e |
|  a     |     f |
|  a     |     x |
|  b     |     c |  // As c is the child of b, all the descendants of c 
|  b     |     d |  // are also descendants of b.
|  b     |     e |
|  b     |     f |
|  b     |     x |
|  c     |     d |
|  c     |     e |
|  c     |     f |
|  c     |     x |
|  d     |     e |
|  d     |     f |
|  d     |     x |
|  e     |     f |
|  e     |     x |
|  f     |     x |
+----+-----------+

Any ideas how to get all the descendants records of a parent? I have tried self join using T1.Child = T2.Parent but the logic did not work.

I am using Teiid VDB which doesn't support Recursive WITH clause.

Answer 1

You need a recursive CTE (common table expression):

with    -- recursive
        -- some DBMS (e.g. Postgres) require the word "recursive"
        -- some others (Oracle, SQL-Server) require omitting the "recursive"
        -- and some (e.g. SQLite) don't bother, i.e. they accept both
descendants
  (parent, descendant, lvl) 
as
  ( select parent, child, 1
    from source
  union all
    select d.parent, s.child, d.lvl + 1
    from descendants  d
      join source  s
        on d.descendant = s.parent
  ) 
select *
from descendants 
order by parent, lvl, descendant ;

See the SQLfiddle. The level I added in not needed. It gives you the "distance" between the parent and the descendant, (1 is child, 2 is grandchild, etc).

Link for the related Teiid documentation about: (recursive) CTEs.

PS: For Oracle:

• LEVEL is a restricted keyword

Answer 2

If you are stuck with this data structure then what you need to use is a recursive CTE: http://www.postgresql.org/docs/8.4/static/queries-with.html
If the documentation isn't clear a quick search may help: tree traversal like this is the most common use for them so you'll find many examples if you search for "recursive common table expression".

There are structures that allow for much more efficient queries of this nature, though they do require extra work to maintain when updates are made. Two common options are:

1. Generating the full path to a node (i.e. /a/b/c) in the tree and storing that in an indexed column. To search this for all under a you can use the predicate LIKE '/a/%, and for those under b use LIKE '/a/b/%'. For a and its descendants, LIKE '/a%'. This is easy to maintain for inserts, but you need to be careful to update the paths (perhaps by trigger) when anything else relevant changes though: for instance if b moves you need to update the stored paths of itself and all its descendants.

2. Storing a graph of distances. So for b store b,b,0, b,a,1 and for c c,c,0, c,b,1, c,a,2 in your relationships table. Again you have some work to do to maintain this when nodes are moved around. This option allows more flexible queries both up and down the tree, and if you SELECT * FROM relationship_graph WHERE distance=1 you have your original tree.

If you have access to a copy (if not I recommend finding it!) have a scan of the Naive Trees chapter of SQL Anitpatterns. That covers this in enough useful detail while being accessible to the less experienced.

If you are unable to alter the structure (as it is an existing system you have little control over) and can't use recursive CTEs, then you'll have to either:

• Use a stored procedure to loop finding nodes until you hit the bottom

• Use something nasty and inefficient, with many joins to the relationship table to pull out the nodes. This will be limited to the depth it can seek, and will always try seek that deep even if it doesn't need to, where all the above options can scan effectively infinite depth.

Answer 3

create table pc ( parent varchar(10), child varchar(10) )

insert into pc values('a','b');
insert into pc values('a','c');
insert into pc values('b','e');
Insert into pc values('b','f');
insert into pc values('a','d');
insert into pc values('b','g');
insert into pc values('c','h');
insert into pc values('c','i');
insert into pc values('d','j');
insert into pc values('f','k');
insert into pc values('x','y');
insert into pc values('y','z');
insert into pc values('m','n');                       

DECLARE @parent varchar(10) = 'a';
WITH cte AS
(
  select null parent, @parent child, 0 as level
   union
  SELECT  a.parent, a.child , 1 as level
    FROM pc a
   WHERE a.parent = @parent
   UNION ALL
  SELECT a.parent, a.child , c.level +    1
    FROM pc a JOIN cte c ON a.parent = c.child
)
SELECT distinct parent, child , level
  FROM cte
 order by level, parent;

This will give you all descendants and the level.

Hope this helps :)

Answer 4

Teiid simply does not support what you want.

• TEIID-3560 - support common table expression with insert/update/delete

Because of that you have to break the VDB abstraction and use a direct query. So factor Teiid out of the equation. What database are you using under the hood?