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 3 4151
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
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
"Vincenzino " <li*@mat.unical .it> wrote in message
news:95******** *************** ***@posting.goo gle.com... 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 thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Varun Kacholia |
last post by:
Hello All,
I wanted to know whether recursive selects are supported in the latest version
of postgres. I checked out the unimplemented sql constructs and came to know
that "with recursive" is supported in 7.3, but i could not find any documentation
for it.
Actually I have a DB containing the adjancency list (ie tuples of type node1 node2...
|
by: Mikito Harakiri |
last post by:
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
|
by: Mikito Harakiri |
last post by:
Transitive closure (TC) of a graph is
with TransClosedEdges (tail, head) as
( select tail, head from Edges
union all
select e.tail, ee.head from Edges e, TransClosedEdges ee
where e.head = ee.tail
)
select distinct * from TransClosedEdges
|
by: David |
last post by:
Hi there,
I'm having some trouble identifying transitive dependencies in the student
table below
StudId Name CourseCode CourseDesc Lecturer Grade Office
'S1234', 'Jack', 'C224', 'Database', 'Codd', 'D', 381
'S1234', 'Jack', 'C225', 'Algorithms', 'Djikstra', 'P', 380
'S2345', 'Jill', 'C224', ...
|
by: birchb |
last post by:
While working on type expressions I am rather stuck for a
way to express recursive types. A simple example of this is a
singly-linked list of integers. In some languages you have compiler
syntax
which suspends evaluation so you can have recursive types. e.g.
typedef Linked_List := int, Linked_List
In LISP I would use a macro.
| |
by: streamkid |
last post by:
hello..
i have the following problem to solve, which is part of mst problem.
i have some nodes (ie cities if you like), and each city is connected
with some other. we don't know which city is connected with what other
city, except for the 1st level (direct connections from city to city).
i want to build the complete map of what is connected...
|
by: karpalmera |
last post by:
Hello! If there’s anyone who can help with this problem…
We created two working environments, creating the same table (TABLEX), same indexes (INDEX1, INDEX2 & INDEX3) and executing the same SQL Statements (SQL1, SQL2 & SQL3) thru spufi. Here is exactly what we did.
For both environments, these SQL statements were created. The ‘where clause’...
|
by: from.future.import |
last post by:
Hi,
I encountered garbage collection behaviour that I didn't expect when
using a recursive function inside another function: the definition of
the inner function seems to contain a circular reference, which means
it is only collected by the mark-and-sweep collector, not by reference
counting. Here is some code that demonstrates it:
===...
|
by: Davy |
last post by:
Hi all,
Sometimes I need to pass same parameter in recursive function. From my
point of view, the style is redundant, and I don't what to use some
global style like self.A, self.B, Is there any other choice?
For example,
def func(self, x, y, A, B, C):
#x, y change in recursive call
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |