Is nonlinear recursion allowed? Does it leverage index?

[Mikito Harakiri]

I wonder if

WITH RECURSIVE MaryAncestor(anc,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?

[Serge Rielau]

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

[Mikito Harakiri]

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,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" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@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

[Serge Rielau]

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

[Mikito Harakiri]

"Serge Rielau" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@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").

[Mikito Harakiri]

"Mikito Harakiri" <mi*********@iahu.com> wrote in message
news:J8*************@news.oracle.com...

"Serge Rielau" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@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,
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_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.

[Serge Rielau]

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

[Mikito Harakiri]

"Serge Rielau" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@hanover.torolab.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),flat(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]

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

Mikito,

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

Cheers,

Jean-Marc

"Mikito Harakiri" <mi*********@iahu.com> a écrit dans le message de
news:dO************@news.oracle.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,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" <sr*****@ca.eye-be-em.com> wrote in message
news:c1**********@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

[--CELKO--]

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

[Ed Avis]

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 <[e-mail]>

[Vadim Tropashko]

Ed Avis wrote:

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

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

http://www.cs.ucla.edu/classes/winte...tes/node3.html