473,322 Members | 1,403 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Is nonlinear recursion allowed? Does it leverage index?

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?


Nov 12 '05 #1
12 3699
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
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,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

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

Nov 12 '05 #5
"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.
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.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"?
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 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?

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*********@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


Nov 12 '05 #10
See why I prefer the nested sets model over hidden navigation via
proprietary code or SQl-99 extensions for trees? :)
Nov 12 '05 #11
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>

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

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

Similar topics

1
by: Endif | last post by:
I am tring to execute the following SQL statements through the Iseries Navigator for DB2/V8.2, But i come up with an error saying recursion is not allowed in common table expression. This is a...
2
by: andrew browning | last post by:
if i write a function to find the max value of an array and want to write it recursively, how do i decide on the base case? i want to say: if (index 0 is the only index then it is max)...
18
by: MTD | last post by:
Hello all, I've been messing about for fun creating a trial division factorizing function and I'm naturally interested in optimising it as much as possible. I've been told that iteration in...
7
by: laniik | last post by:
Hi, I am looking for a way to do nonlinear minimization in c++ (c is acceptable also) with constraints (a la minimize f() with parameters x,y such that x+y<1) or somthing.. I was wondering if...
13
by: robert | last post by:
My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception. What...
6
by: Andre Kempe | last post by:
hej folks. i have a heap with fixed size and want to determine the depth of a element with given index at compile-time. therefore i wrote some templates. however, when i use template...
12
by: NOO Recursion | last post by:
Hi everyone! I am trying to write a program that will search a 12x12 for a thing called a "blob". A blob in the grid is made up of asterisks. A blob contains at least one asterisk. If an...
14
nurulshidanoni
by: nurulshidanoni | last post by:
DEAL ALL EXPERTS, How can i write random nonlinear function? Let say, the nonlinear is 2 x power of 3. But , I want the random function of nonlinear. Thank you. Ashida.
30
by: Jeff Bigham | last post by:
So, it appears that Javascript has a recursion limit of about 1000 levels on FF, maybe less/more on other browsers. Should such deep recursion then generally be avoided in Javascript?...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.