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

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message news:J87%b.23$OB.162_at_news.oracle.com...
> "Serge Rielau" <srielau_at_ca.eye-be-em.com> wrote in message
> news:c1innt$hgv$1_at_hanover.torolab.ibm.com...
> > Mikito Harakiri wrote:
> > >
> > > 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?
> > >
> > Good question. I remember a thread in the Oracle newsgroup that
> > concluded that the standard version was more powerful, but that was
> > hardly based on a mathematical proof.
> > Also note that O10g has made changes to connect by.
> >
> > There is one thing I can say with confidence:
> > Rewriting one as the other is in general non trivial.
> >
> > Things are getting interesting when you try to tease order and level
> > information out of "recursive with".
> > Given that I never wrote anything using connect by I can't comment where
> > connect by stumbles.
>
> How about "same generation"?
>
> sg(X,X) <- person(X)
> sg(X,Y) <- parent(X,Z), sg(Z,W), parent(Y,W)
>
> For example
>
> parent(X,Y)
> -------
> 1 3
> 1 3
> 3 4
> 2 5
> 4 5
>
> would produce
>
> sg(X,Y)
> -------
> 1 1
> 2 2
> 3 3
> 4 4
> 5 5
> 2 3
> 4 5
>
> There is no difficulty translating this Datalog into "recursive with", but
> how do approach this problem with "connect by"? (Hint: I made the graph
been
> non-balanced on purpose: to eliminate any futile attemplts leveraging
> "level").

It takes a while to understand all those goofy pseudocolumns. The critical idea is running

select sys_connect_by_path('['||X||','||Y||')', '.'),
connect_by_root(X),connect_by_root(Y),
connect_by_isleaf,

then we see that, essentially, oracle outputs all the paths with CONNECT_BY_ROOT(X) being the beginning of the path, Y being the end, and level is the length of the path. Of course, every pseudocolumn is redundant, as all of them can be derived from path (Except connect_by_isleaf which could be computed by scalar subquery in the select clause; not an efficient proposition:-(

Having said that, same generation is just a selfjoin on the top of this view with additional a.level=b.level restriction -- ugly, but doable. Received on Wed Feb 25 2004 - 21:21:26 CET