Is nonlinear recursion allowed? Does it leverage index?

**Serge Rielau** · Nov 12 '05, 06:54 AM

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

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(an c,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

**Mikito Harakiri** · Nov 12 '05, 06:54 AM

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

From

404 Not Found

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,de sc) 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>XM L 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@ca.e ye-be-em.com> wrote in message
news:c1h3fh$kdo $1@hanover.toro lab.ibm.com...[color=blue]
> 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(an c,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[/color]

**Serge Rielau** · Nov 12 '05, 06:54 AM

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

Mikito Harakiri wrote:[color=blue]
>
> 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?
>[/color]
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.

Cheers
Serge

--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab

**Mikito Harakiri** · Nov 12 '05, 06:55 AM

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

"Serge Rielau" <srielau@ca.e ye-be-em.com> wrote in message
news:c1innt$hgv $1@hanover.toro lab.ibm.com...[color=blue]
> Mikito Harakiri wrote:[color=green]
> >
> > BTW, I'm comparing "connect by" and "recursive with". Is there a query[/color][/color]
that[color=blue][color=green]
> > can be expressed in the one and cannot in the other?
> >[/color]
> 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.[/color]

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").

**Mikito Harakiri** · Nov 12 '05, 06:55 AM

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

"Mikito Harakiri" <mikharakiri@ia hu.com> wrote in message
news:J87%b.23$O B.162@news.orac le.com...[color=blue]
> "Serge Rielau" <srielau@ca.e ye-be-em.com> wrote in message
> news:c1innt$hgv $1@hanover.toro lab.ibm.com...[color=green]
> > Mikito Harakiri wrote:[color=darkred]
> > >
> > > BTW, I'm comparing "connect by" and "recursive with". Is there a query[/color][/color]
> that[color=green][color=darkred]
> > > can be expressed in the one and cannot in the other?
> > >[/color]
> > 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.[/color]
>
> 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[/color]
been[color=blue]
> non-balanced on purpose: to eliminate any futile attemplts leveraging
> "level").[/color]

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_isle af,
level,p.*
from parent p connect by prior Y = X

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_isle af 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.

**Serge Rielau** · Nov 12 '05, 06:55 AM

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

You should post in oracle.server
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab

**Mikito Harakiri** · Nov 12 '05, 06:55 AM

Is "connec t by" equivalent to "recurs ive with" (was Re: Is nonlinear recursion...)

"Serge Rielau" <srielau@ca.e ye-be-em.com> wrote in message
news:c1j058$i6i $1@hanover.toro lab.ibm.com...[color=blue]
> You should post in oracle.server[/color]

Not sure what is the best oracle place for SQL questions: I thought that
"server" is occupied by masters of segments and extents. I'm certain neither
group can spell "Datalog" anyway.

Anyway, here is the latest about same generation. Example from the Page 312
of the Alice Book

rsg(x,y) <- flat(x,y)
rsg(x,y) <- up(x,x1),rsg(y1 ,x1),down(y1,y)

looks very challenging for "connect by".

However, let

up^*(x,y,n)

and

down^*(x,y,n)

be transitive closure of up(x,y), and down(x,y), correspondingly , where n is
the length of the path (so that if you have 2 paths of different lenght
connecting x and y, then you have 2 tuples in up^* relation). Then,

rsg(x,y) <- up^*(x,x1,n1),f lat(y1,x1),down ^*(y1,y,n2),n1= n2

which is no-brainer for "connect by".

Therefore, the question still is "Is connect-by less expressive than
recursive-with"?

**Vadim Tropashko** · Nov 12 '05, 06:55 AM

Re: Is "connec t by" equivalent to "recurs ive with" (was Re: Is nonlinearrecurs ion...)

Mikito Harakiri wrote:[color=blue]
> Therefore, the question still is "Is connect-by less expressive than
> recursive-with"?[/color]

For linear Datalog programs (=ANSI SQL?) it seems to be.

Datalog program is called linear if each recursiuve clause has at most
one of the predicates from the ones appeared in the heads of the rule.
Therefore, rules could be partitioned into classes like that

p <- a_11,...,a_k1, p , a_(k1+1), ..., a_n1
p <- a_21,...,a_k2, p , a_(k2+1), ..., a_n2
....
p <- b_1,...,b_m1
p <- b_2,...,b_m2
....

where all As and Bs are predicates that can't appear in any rule heads.
Then, let

U be an answer for

U <- b_1,...,b_m1
U <- b_2,...,b_m2
....

which is relationally nothing more than a union of select-project-join
queries.

Next, let

A_1k <- a_11,...,a_k1
A_1n <- a_(k1+1), ..., a_n1
....

and

A_1k^*(length)
A_1n^*(length)

be relational closures of these. Substituting all these we finally
express p nonrecursively:

p <- A_1k^*(length), U , A_1n^*(length)
p <- A_2k^*(length), U , A_2n^*(length)

Nothing more than straightforward generalization of Mikito's
"reverse-same-generation" example.

Is everything correct in this "proof"? Don't variables (which were
skipped for simplicity) pose any subtle problem?

**Jean-Marc Blaise** · Nov 12 '05, 06:55 AM

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@ia hu.com> a écrit dans le message de
news:dO4%b.12$O B.91@news.oracl e.com...[color=blue]
> From
>
> http://www-db.stanford.edu/~widom/cs...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,de sc) 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>XM L 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[/color]
fixed-point[color=blue]
> faster than linear version" makes any sence from practical perspective.[/color]
Yes,[color=blue]
> we can build transitive closure faster, but the execution here doesn't[/color]
need[color=blue]
> 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[/color]
that[color=blue]
> can be expressed in the one and cannot in the other?
>
> "Serge Rielau" <srielau@ca.e ye-be-em.com> wrote in message
> news:c1h3fh$kdo $1@hanover.toro lab.ibm.com...[color=green]
> > 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(an c,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[/color]
>
>[/color]

**--CELKO--** · Nov 12 '05, 06:56 AM

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

See why I prefer the nested sets model over hidden navigation via
proprietary code or SQl-99 extensions for trees? :)

**Ed Avis** · Nov 12 '05, 06:56 AM

Re: Is "connec t by" equivalent to "recurs ive with" (was Re: Is nonlinear recursion...)

What you discuss about Datalog programs and their translation into
'recursive with' queries sounds interesting. Is there an introduction
to this subject you can recommend? (I've searched the web but I do
not know where to start reading - perhaps the best place is a book you
could suggest.)

--
Ed Avis <ed@membled.com >

**Vadim Tropashko** · Nov 12 '05, 06:56 AM

Re: Is "connec t by" equivalent to "recurs ive with" (was Re: Is nonlinearrecurs ion...)

Ed Avis wrote:[color=blue]
> What you discuss about Datalog programs and their translation into
> 'recursive with' queries sounds interesting. Is there an introduction
> to this subject you can recommend? (I've searched the web but I do
> not know where to start reading - perhaps the best place is a book you
> could suggest.)[/color]

Datalog Chapter in the Alice Book (Abiteboul&Hull &Vianu)? Googling
"Recursive SQL" also brought up this link:

Part III. Complex Queries and Reasoning

http://www.cs.ucla.edu/classes/winter04/cs240A/notes/node3.html

Is nonlinear recursion allowed? Does it leverage index?

Is nonlinear recursion allowed? Does it leverage index?

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment