Thread: Getting to grips with Recursive CTEs.

Hi all,

I'm trying to get to grips with Recursive CTEs.

I have a problem that I can't appear to solve using them.

I have data like this - fiddle here full data + table at the end of
the question and in the fiddle
https://dbfiddle.uk/?rdbms=postgres_11&fiddle=955a33fe6bd63302da5e8801eb7bbd98
or see bottom of this question.


CREATE TABLE tree (parent varchar(10), child varchar(10));

Sample.
('a','b'),
('a','c'),
('b','e'),
('b','f'),

So a is the parent of b and b is the parent of e, so I'd like records like

a, b
a, c
a, e
a, f
and so on - i.e. no matter how far down into the tree you are, I want
to list child x with all its ancestors as separate records.

Now, I'm managed to get this far

WITH rcte (child, parent) AS
(
  SELECT parent AS child, NULL AS parent FROM tree t1
    WHERE Parent NOT IN (SELECT child FROM tree)
  UNION ALL

  SELECT t2.child, t3.parent FROM tree t2
  JOIN tree t3 ON t2.parent >= t3.parent
  -- ORDER BY child
)
SELECT DISTINCT * FROM rcte
ORDER BY parent NULLS FIRST, child;

But that just appears to produce a CROSS JOIN between the parents and
children excluding records where the parent is bigger than the child -
which is obviously not possible.

Sample of my results

parent child
a
m
x
a b
a c

This is OK, but as you can see m and x don't have any parents, but then we have

m n
m y
m z

but the tuple (m,n) is a free standing record and the only one
involving these two variables, so (m, n) is correct but (m,y) and (m,
z) aren't.

I would also like the level to appear in a third column but I can't
seem to get that either. The SQL Server fiddle (same data) here
(https://dbfiddle.uk/?rdbms=sqlserver_2017&fiddle=6c57c670b7f3a7aaa74b08b6bd897652)
shows what I am trying to do - but even this only works for the base
level with a wierd syntax.

I would be particularly grateful for explanations, esp to any URLs &c.
to give me pointers here - I have obviously done my own searches but
these have proved fruitless so far.

Should you require any further information, please don't hesitate to
get back to me here.

TIA and rgs,

Pól...

TABLE, data and query.

CREATE TABLE tree (parent VARCHAR(10), child VARCHAR(10));

INSERT INTO tree VALUES ('a','b'), ('a','c'), ('b','e'), ('b','f'),
('a','d'), ('b','g'),
('c','h'), ('c','i'), ('d','j'), ('f','k'), ('x','y'), ('y','z'), ('m','n');

WITH rcte (child, parent) AS
(
  SELECT parent AS child, NULL AS parent FROM tree t1
    WHERE Parent NOT IN (SELECT child FROM tree)
  UNION ALL

  SELECT t2.child, t3.parent FROM tree t2
  JOIN tree t3 ON t2.parent >= t3.parent

)
SELECT DISTINCT parent, child FROM rcte
ORDER BY parent NULLS FIRST, child;

=?UTF-8?B?UMOzbCBVYSBMYW/DrW5lY2jDoWlu?= <linehanp@tcd.ie> writes:
> I'm trying to get to grips with Recursive CTEs.
> I have a problem that I can't appear to solve using them.
> ... no matter how far down into the tree you are, I want
> to list child x with all its ancestors as separate records.

I think what you want is something like this:

with recursive rcte(parent,child) as (
(
 select parent,child from tree
 union all
 select null::varchar(10),parent from tree
   where parent not in (select child from tree)
)
union all
select t3.parent, t2.child from tree t2
  join rcte t3 on t2.parent = t3.child
)
select distinct * from rcte
order by parent nulls first, child;

The way to think about recursive CTEs, in cases like this one,
is "set up your base-case facts in the nonrecursive term, then
in the recursive term, compute whatever new facts can be derived
from an existing fact".  So your base facts are the tree rows
themselves, plus you'd like dummy rows with null parent for any
parents that have no children, giving the nonrecursive term

(
 select parent,child from tree
 union all
 select null::varchar(10),parent from tree
   where parent not in (select child from tree)
)

(The extra parens might not really be necessary, but I'm just
making sure that the parser will see this whole thing as the
nonrecursive term, and not maybe split the query at the first
UNION.)

Then the recursive term takes each known fact (rcte row)
and tries to extend it by one level of child relationship:

select t3.parent, t2.child from tree t2
  join rcte t3 on t2.parent = t3.child

The recursive-CTE mechanism takes care of repeatedly applying
this rule to go as far down the tree as necessary.  It also
takes care of preventing infinite recursion --- if, for instance,
you had circular relationships in "tree" --- by dint of throwing
away duplicate rows.  I think therefore that the DISTINCT in
the calling query should not really be necessary.  It is needed
in this query as it stands, but I suspect that's only because
the nonrecursive term itself generates some duplicates.  If
you change the inner "union all" to "union" so that there's
no duplicates at the start of the recursion, it seems like the
calling DISTINCT can be dropped.  (I'm too caffeine-deprived
to be quite sure if that's correct in general, but it seems to
be true for this data set at least.)

            regards, tom lane

Hola Miquel,

y gracias por tu contribución,

> You are not using a recursive function because it is needed to call the table "rcte" in the UNION ALL
> But it will fail because t3.parent is null at the beginning, so try this another one

> WITH rcte (child, parent) AS
> (
>   SELECT parent AS child, '' AS parent FROM tree t1
>     WHERE Parent NOT IN (SELECT child FROM tree)
>   UNION ALL
>   SELECT t2.child, t3.parent FROM tree t2
>   JOIN rcte t3 ON t2.parent >= t3.parent
> )

> I haven't tried.

That's great - I've played around with it a wee bit - still have a lot
to learn! :-)

Haven't had too much time - but I think it's slowly dawning on me.

Best regards,

Pól...

Hi Tom,

> I think what you want is something like this:

< detailled and thoughtful explanation snipped >

Wow! A lot to digest - I'm gradually grasping the concept and thank
you so much for your input!

Best regards,

Pól...