Re: Is nonlinear recursion allowed? Does it leverage index?

From

http://www-db.stanford.edu/~widom/cs145/notes/recursion.html

<quote>
Nonlinear recursion
SQL-99 only requires support of "linear" recursion: each FROM has at most one reference to a recursively-defined relation. Example: Nonlinear version of Ancestor:

  WITH RECURSIVE Ancestor(anc,desc) AS

         ( (SELECT parent as anc, child as desc FROM ParentOf)
           UNION
           (SELECT A1.anc, A2.desc
            FROM Ancestor A1, Ancestor A2
            WHERE A1.desc = A2.anc) )

All I did was manually pushing single table predicate desc = "Mary" inside view definition.

Now I doubt that statement "Executing it literally converges to fixed-point faster than linear version" makes any sence from practical perspective. Yes, we can build transitive closure faster, but the execution here doesn't need full transitive closure; only path from node to the root.

It looks like theory and practice aren't in harmony here:-)

BTW, I'm comparing "connect by" and "recursive with". Is there a query that can be expressed in the one and cannot in the other?

"Serge Rielau" <srielau_at_ca.eye-be-em.com> wrote in message news:c1h3fh$kdo$1_at_hanover.torolab.ibm.com...
> Mikito,
>
> I'm not sure I understand the query in the first place.
> I don't seem to see where you navigate up the tree.
>
> In DB2 recursion must use UNION ALL. I don't think you can recurse using
> the recursive common table expression twice.
>
> Here is how I would write it:
>
> WITH MaryAncestor(anc,desc) AS
> ( (SELECT parent as anc, child as desc
> FROM ParentOf WHERE desc = "Mary")
> UNION ALL
> (SELECT P.anc, A.desc
> FROM MaryAncestor A, ParentOf P WHERE A.anc = P.desc) )
> SELECT anc FROM MaryAncestor
>
> (something like that at least...)
>
> Cheers
> Serge
> --
> Serge Rielau
> DB2 SQL Compiler Development
> IBM Toronto Lab
Received on Wed Feb 25 2004 - 18:09:33 CET