6

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.

  • 3
    According to the docs, Teiid does support recursive queries, you just need to omit the keyword RECURSIVE. (And while we are at it, you probably also need to get more acquainted with the manual.) Anyway, tagging your question with the wrong database system and not tagging it with the actual one is why you get the wrong answer. – Andriy M Mar 11 '15 at 10:19
  • Teiid VDB is a virtualization layer that reveals the underlying database. What database are you using? "A virtual database (or VDB) is a container for components used to integrate data from multiple data sources, so that they can be accessed in an integrated manner through a single, uniform API. " – Evan Carroll Dec 31 '18 at 18:18
13

You need a recursive CTE (common table expression):

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

4

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.

0
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 :)

  • 1
    You are missing a terminator (after create table ;) – ypercubeᵀᴹ Dec 15 '17 at 10:16
0

Teiid simply does not support what you want.

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?

protected by Community Mar 2 at 5:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.