Recursive queries in SQL3 and graph transitive closure

[Vincenzino]

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

[Serge Rielau]

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

[Knut Stolze]

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

[John Gilson]

"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