473,991 Members | 2,858 Online

# Is nonlinear recursion allowed? Does it leverage index?

I wonder if

WITH RECURSIVE MaryAncestor(an c,desc) AS
( (SELECT parent as anc, child as desc FROM ParentOf WHERE desc =
"Mary")
UNION
(SELECT A1.anc, A2.desc
FROM MaryAncestor A1, MaryAncestor A2
WHERE A1.desc = A2.anc) )
SELECT anc FROM MaryAncestor

is allowed in DB2 in the first place. If allowed, can it leverage join index
when navigating path from "Mary" node to ancestor root?

Nov 12 '05 #1
12 3771
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
Nov 12 '05 #2
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 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" <sr*****@ca.e ye-be-em.com> wrote in message
news:c1******** **@hanover.toro lab.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(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

Nov 12 '05 #3
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.

Cheers
Serge

--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
Nov 12 '05 #4
"Serge Rielau" <sr*****@ca.e ye-be-em.com> wrote in message
news:c1******** **@hanover.toro lab.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.

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

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

Nov 12 '05 #5
"Mikito Harakiri" <mi*********@ia hu.com> wrote in message
news:J8******** *****@news.orac le.com...
"Serge Rielau" <sr*****@ca.e ye-be-em.com> wrote in message
news:c1******** **@hanover.toro lab.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.

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

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_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.
Nov 12 '05 #6
You should post in oracle.server
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
Nov 12 '05 #7
"Serge Rielau" <sr*****@ca.e ye-be-em.com> wrote in message
news:c1******** **@hanover.toro lab.ibm.com...
You should post in oracle.server

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"?
Nov 12 '05 #8
Mikito Harakiri wrote:
Therefore, the question still is "Is connect-by less expressive than
recursive-with"?

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

Nov 12 '05 #9
Mikito,

The following article in Developer Domain might interest you
http://www-106.ibm.com/developerwork...steinbach.html

Cheers,

Jean-Marc

"Mikito Harakiri" <mi*********@ia hu.com> a écrit dans le message de
news:dO******** ****@news.oracl e.com...
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 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" <sr*****@ca.e ye-be-em.com> wrote in message
news:c1******** **@hanover.toro lab.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(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

Nov 12 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.