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

Mikito,

The following article in Developer Domain might interest you http://www-106.ibm.com/developerworks/db2/library/techarticle/0307steinbach/0307steinbach.html

Cheers,

Jean-Marc

"Mikito Harakiri" <mikharakiri_at_iahu.com> a écrit dans le message de news:dO4%b.12$OB.91_at_news.oracle.com...
> 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) )
> SELECT anc FROM Ancestor WHERE desc = "Mary"
>
> a.. Looks cleaner
> b.. Executing it literally converges to fixed-point faster than linear
> version
> </quote><aside>XML still sucks</aside>
>
> 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 Thu Feb 26 2004 - 08:11:01 CET