Re: Getting to grips with Recursive CTEs.

=?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