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? 12 3596
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
From http://wwwdb.stanford.edu/~widom/cs...recursion.html
<quote>
Nonlinear recursion
SQL99 only requires support of "linear" recursion: each FROM has at most
one reference to a recursivelydefined 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 fixedpoint 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 fixedpoint
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.eyebeem.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
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
"Serge Rielau" <sr*****@ca.eyebeem.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
nonbalanced on purpose: to eliminate any futile attemplts leveraging
"level").
"Mikito Harakiri" <mi*********@iahu.com> wrote in message
news:J8*************@news.oracle.com... "Serge Rielau" <sr*****@ca.eyebeem.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 nonbalanced 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.
You should post in oracle.server

Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
"Serge Rielau" <sr*****@ca.eyebeem.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 nobrainer for "connect by".
Therefore, the question still is "Is connectby less expressive than
recursivewith"?
Mikito Harakiri wrote: Therefore, the question still is "Is connectby less expressive than recursivewith"?
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 selectprojectjoin
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
"reversesamegeneration" example.
Is everything correct in this "proof"? Don't variables (which were
skipped for simplicity) pose any subtle problem?
Mikito,
The following article in Developer Domain might interest you http://www106.ibm.com/developerwork...steinbach.html
Cheers,
JeanMarc
"Mikito Harakiri" <mi*********@iahu.com> a écrit dans le message de
news:dO************@news.oracle.com... From
http://wwwdb.stanford.edu/~widom/cs...recursion.html
<quote> Nonlinear recursion SQL99 only requires support of "linear" recursion: each FROM has at most one reference to a recursivelydefined 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 fixedpoint 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
fixedpoint 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.eyebeem.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
See why I prefer the nested sets model over hidden navigation via
proprietary code or SQl99 extensions for trees? :)
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>
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 This discussion thread is closed Replies have been disabled for this discussion. Similar topics
1 post
views
Thread by Endif 
last post: by

2 posts
views
Thread by andrew browning 
last post: by

18 posts
views
Thread by MTD 
last post: by

7 posts
views
Thread by laniik 
last post: by

13 posts
views
Thread by robert 
last post: by

6 posts
views
Thread by Andre Kempe 
last post: by

12 posts
views
Thread by NOO Recursion 
last post: by
 
30 posts
views
Thread by Jeff Bigham 
last post: by
          