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  
Share this Question
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  
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  
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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3468
 replies: 3
 date asked: Nov 12 '05
