By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,631 Members | 826 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,631 IT Pros & Developers. It's quick & easy.

Recursive queries in SQL3 and graph transitive closure

P: n/a
Hi, I have some problem in using SQL3 recursive queries on DB2
database system (8.1 and 8.2 UDB).
I need to compute the transitive closure of a (possibly) ciclic graph
using SQL3 on DB2.
I MUST use pure SQL3 and I cannot use cursors, indexes and the like.

The graph is represented by a set of arcs with the table "arc"
having two attributes "a1" and "a2" for source and target nodes resp.

The SQL3 query I'm using is the following:

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

I have that:
1)using the following graph (represented by the "arc" table), the SQL3
query above works fine
"arc"
1, 2
2, 3
3, 4
4, 5
5, 1
i.e. if the overall graph is a cycle, the query works well. However:

2) if I use the following graph, the SQL3 computation "fails", i.e.
DB2 doesn't send any error but the query does not return any result
within one hour (after this I stopped the query)
"arc"
1, 2
2, 1
2, 3
3, 4

3) Similarly, if I use the following graph, the SQL3 computation
"fails" (as in point 2)
"arc"
1, 2
2, 3
3, 2
3, 4

I tried also other graph configurations but I have the same problems
as in 2) and 3).

I tried to change the query in (I capitalize modifications to
highlight them)

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select DISTINCT e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

or

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1
AND (e.a1, p.att2) NOT IN (SELECT * FROM path) )
select distinct att1, att2
from path
group by att1

but the system gives syntactical errors.

Could you help me to solve this problem? So far I found that DB2 is
the only database working with cyclic graphs and recursive queries
over them (point 1) but I need to solve queries over graphs of type 2)
and 3) .

Could you tell me where (and if) the query is wrong?

Regards
Nov 12 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Vincenzino wrote:
Hi, I have some problem in using SQL3 recursive queries on DB2
database system (8.1 and 8.2 UDB).
I need to compute the transitive closure of a (possibly) ciclic graph
using SQL3 on DB2.
I MUST use pure SQL3 and I cannot use cursors, indexes and the like.

The graph is represented by a set of arcs with the table "arc"
having two attributes "a1" and "a2" for source and target nodes resp.

The SQL3 query I'm using is the following:

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

I have that:
1)using the following graph (represented by the "arc" table), the SQL3
query above works fine
"arc"
1, 2
2, 3
3, 4
4, 5
5, 1
i.e. if the overall graph is a cycle, the query works well. However:

2) if I use the following graph, the SQL3 computation "fails", i.e.
DB2 doesn't send any error but the query does not return any result
within one hour (after this I stopped the query)
"arc"
1, 2
2, 1
2, 3
3, 4

3) Similarly, if I use the following graph, the SQL3 computation
"fails" (as in point 2)
"arc"
1, 2
2, 3
3, 2
3, 4

I tried also other graph configurations but I have the same problems
as in 2) and 3).

I tried to change the query in (I capitalize modifications to
highlight them)

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select DISTINCT e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

or

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1
AND (e.a1, p.att2) NOT IN (SELECT * FROM path) )
select distinct att1, att2
from path
group by att1

but the system gives syntactical errors.

Could you help me to solve this problem? So far I found that DB2 is
the only database working with cyclic graphs and recursive queries
over them (point 1) but I need to solve queries over graphs of type 2)
and 3) .

Could you tell me where (and if) the query is wrong?

Regards

Since the graph can be cyclic the simplest fix would be to add an
artificial "timeout".
E.g. add a column "level" which starts with 0
recurse using level + 1 as level
and then add an "AND level < 10000"
That will limit DB2 to 10000 levels of recursion (which ought to be
plenty for most apps - even my reports to chain is shorter ;-)

Cheers
Serge
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab
Nov 12 '05 #2

P: n/a
Vincenzino wrote:
Hi, I have some problem in using SQL3 recursive queries on DB2
database system (8.1 and 8.2 UDB).
I need to compute the transitive closure of a (possibly) ciclic graph
using SQL3 on DB2.
I MUST use pure SQL3 and I cannot use cursors, indexes and the like.
That sounds very much like an exercise. ;-)
The graph is represented by a set of arcs with the table "arc"
having two attributes "a1" and "a2" for source and target nodes resp.

The SQL3 query I'm using is the following:

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

I have that:
1)using the following graph (represented by the "arc" table), the SQL3
query above works fine
"arc"
1, 2
2, 3
3, 4
4, 5
5, 1
i.e. if the overall graph is a cycle, the query works well. However:

2) if I use the following graph, the SQL3 computation "fails", i.e.
DB2 doesn't send any error but the query does not return any result
within one hour (after this I stopped the query)
"arc"
1, 2
2, 1
Here you have a cycle already.

Either you choose the approach suggested by Serge and implement an explicit
termination, or you must collect the path to each vertex and before
extending the path you will check if the vertex already exists in the path
so far.
2, 3
3, 4


--
Knut Stolze
Information Integration
IBM Germany / University of Jena
Nov 12 '05 #3

P: n/a
"Vincenzino" <li*@mat.unical.it> wrote in message
news:95**************************@posting.google.c om...
Hi, I have some problem in using SQL3 recursive queries on DB2
database system (8.1 and 8.2 UDB).
I need to compute the transitive closure of a (possibly) ciclic graph
using SQL3 on DB2.
I MUST use pure SQL3 and I cannot use cursors, indexes and the like.

The graph is represented by a set of arcs with the table "arc"
having two attributes "a1" and "a2" for source and target nodes resp.

The SQL3 query I'm using is the following:

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

I have that:
1)using the following graph (represented by the "arc" table), the SQL3
query above works fine
"arc"
1, 2
2, 3
3, 4
4, 5
5, 1
i.e. if the overall graph is a cycle, the query works well. However:

2) if I use the following graph, the SQL3 computation "fails", i.e.
DB2 doesn't send any error but the query does not return any result
within one hour (after this I stopped the query)
"arc"
1, 2
2, 1
2, 3
3, 4

3) Similarly, if I use the following graph, the SQL3 computation
"fails" (as in point 2)
"arc"
1, 2
2, 3
3, 2
3, 4

I tried also other graph configurations but I have the same problems
as in 2) and 3).

I tried to change the query in (I capitalize modifications to
highlight them)

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select DISTINCT e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1)
select distinct att1, att2
from path
group by att1

or

with path (att1, att2) as (
select e.a1, e.a2
from arc e
union all
select e.a1, p.att2
from arc e, path p
where e.a2 = p.att1 and p.att2 <> e.a1
AND (e.a1, p.att2) NOT IN (SELECT * FROM path) )
select distinct att1, att2
from path
group by att1

but the system gives syntactical errors.

Could you help me to solve this problem? So far I found that DB2 is
the only database working with cyclic graphs and recursive queries
over them (point 1) but I need to solve queries over graphs of type 2)
and 3) .

Could you tell me where (and if) the query is wrong?

Regards


See http://tinyurl.com/3zb36

--
JAG
Nov 12 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.