I have graph
x y
- -
1 2
2 3
3 1
4 5
and would like to query how many connected components it has (two in
the example -- {1,2,3} and {4,5}). Is it doable with "recursive with"? 9 1956
I don't know graph theory. So, there must be more sophiscated
algorithm.
Anyway, here is a trial code. It will be better to test with more data.
CREATE TABLE connected
(x SMALLINT NOT NULL
,y SMALLINT NOT NULL
)
;
INSERT INTO connected
VALUES
(1, 2)
,(2, 3)
,(3, 1)
,(4, 5)
;
------------------------- Commands Entered -------------------------
WITH
OrderedNumber (n) AS (
SELECT n1*10 + n2
FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1)
, (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2)
WHERE n1*10 + n2 < 100
)
,
Recurse (seq, y, con) AS (
SELECT 0, y
, CAST(CASE
WHEN x < y THEN
'00,' || SUBSTR(DIGITS(x),4,2) || ',' ||
SUBSTR(DIGITS(y),4,2)
ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' ||
SUBSTR(DIGITS(x),4,2)
END
AS VARCHAR(20)
)
FROM connected
UNION ALL
SELECT seq + 1
, new.y
, SUBSTR(con,1,ni-1) || ',' || SUBSTR(DIGITS(new.y),4,2) ||
SUBSTR(con,ni)
FROM Recurse old
, connected new
, TABLE
(SELECT MAX((n+1)*3)
FROM OrderedNumber odn
WHERE
LOCATE(SUBSTR(DIGITS(new.y),4,2),con) = 0
AND (CASE
WHEN n < (LENGTH(con)+1)/3 THEN
SMALLINT(SUBSTR(con,n*3+1,2))
ELSE 99
END) < new.y
) p(ni)
WHERE seq < 100
AND old.y = new.x
AND p.ni IS NOT NULL
)
,ContainedNode AS (
SELECT s
, con
, SUBSTR(con,n*3+1,2) node
, (LENGTH(c.con)+1)/3 max_n
FROM (SELECT con
, INT(ROWNUMBER() OVER()) s
FROM (SELECT DISTINCT SUBSTR(a.con,4)
FROM Recurse a
) b(con)
) c(con, s)
, TABLE
(SELECT n
FROM OrderedNumber d
WHERE d.n <= LENGTH(c.con)/3
) e
)
SELECT DISTINCT con AS Connected
FROM ContainedNode a
WHERE
NOT EXISTS
(SELECT *
FROM ContainedNode c
WHERE c.s <> a.s
AND c.node = a.node
AND c.max_n >= a.max_n
)
ORDER BY
con
;
--------------------------------------------------------------------
CONNECTED
--------------------
01,02,03
04,05
2 record(s) selected.
If I added following data, previous sample code produced incorrect
rsults.
INSERT INTO connected
VALUES
(6, 8)
,(7, 8)
,(8, 9)
,(8,10)
,(9,10)
;
This is a revised sample. I hope that no more error exist.
------------------------- Commands Entered -------------------------
WITH
OrderedNumber (n) AS (
SELECT n1*10 + n2
FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1)
, (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2)
WHERE n1*10 + n2 < 100
)
,
Biconnected (x, y) AS (
SELECT *
FROM connected
UNION
SELECT y, x
FROM connected
)
,
Recurse (seq, y, nodes, link) AS (
SELECT 0, y
, CAST(CASE
WHEN x < y THEN
'00,' || SUBSTR(DIGITS(x),4,2) || ',' ||
SUBSTR(DIGITS(y),4,2)
ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' ||
SUBSTR(DIGITS(x),4,2)
END
AS VARCHAR(20)
)
, CAST('0000,'||SUBSTR(DIGITS(x),4,2)||SUBSTR(DIGITS (y),4,2) AS
VARCHAR(100))
FROM Biconnected
UNION ALL
SELECT seq + 1
, new.y
, SUBSTR(nodes,1,(n+1)*3-1)
|| CASE
WHEN SMALLINT(SUBSTR(nodes,n*3+1,2)) = new.y THEN
''
ELSE ',' || SUBSTR(DIGITS(new.y),4,2)
END
|| SUBSTR(nodes,(n+1)*3)
, link || ',' ||
SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(new.y),4, 2)
FROM Recurse old
, Biconnected new
, TABLE
(SELECT MAX(n)
FROM OrderedNumber odn
WHERE
LOCATE(SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(ne w.y),4,2),link) = 0
AND
(CASE
WHEN n < (LENGTH(nodes)+1)/3 THEN
SMALLINT(SUBSTR(nodes,n*3+1,2))
ELSE 99
END) <= new.y
) p(n)
WHERE seq < 100
AND old.y = new.x
AND p.n IS NOT NULL
)
,
ContainedNode AS (
SELECT s
, nodes
, SUBSTR(nodes,n*3+1,2) node
, (LENGTH(c.nodes)+1)/3 max_n
FROM (SELECT nodes
, INT(ROWNUMBER() OVER()) s
FROM (SELECT DISTINCT SUBSTR(a.nodes,4)
FROM Recurse a
) b(nodes)
) c(nodes, s)
, TABLE
(SELECT n
FROM OrderedNumber d
WHERE d.n <= LENGTH(c.nodes)/3
) e
)
SELECT DISTINCT nodes AS Connected_Nodes
FROM ContainedNode a
WHERE
NOT EXISTS
(SELECT *
FROM ContainedNode c
WHERE c.s <> a.s
AND c.node = a.node
AND c.max_n >= a.max_n
)
ORDER BY
Connected_Nodes
;
-------------------------------------------------------------------------
CONNECTED_NODES
--------------------
01,02,03
04,05
06,07,08,09,10
3 record(s) selected.
Tonkuma wrote: If I added following data, previous sample code produced incorrect rsults. INSERT INTO connected VALUES (6, 8) ,(7, 8) ,(8, 9) ,(8,10) ,(9,10) ;
This is a revised sample. I hope that no more error exist. ------------------------- Commands Entered ------------------------- WITH OrderedNumber (n) AS ( SELECT n1*10 + n2 FROM (VALUES 0,1,2,3,4,5,6,7,8,9) p1(n1) , (VALUES 0,1,2,3,4,5,6,7,8,9) p2(n2) WHERE n1*10 + n2 < 100 ) , Biconnected (x, y) AS ( SELECT * FROM connected UNION SELECT y, x FROM connected ) , Recurse (seq, y, nodes, link) AS ( SELECT 0, y , CAST(CASE WHEN x < y THEN '00,' || SUBSTR(DIGITS(x),4,2) || ',' || SUBSTR(DIGITS(y),4,2) ELSE '00,' || SUBSTR(DIGITS(y),4,2) || ',' || SUBSTR(DIGITS(x),4,2) END AS VARCHAR(20) ) , CAST('0000,'||SUBSTR(DIGITS(x),4,2)||SUBSTR(DIGITS (y),4,2) AS VARCHAR(100)) FROM Biconnected UNION ALL SELECT seq + 1 , new.y , SUBSTR(nodes,1,(n+1)*3-1) || CASE WHEN SMALLINT(SUBSTR(nodes,n*3+1,2)) = new.y THEN '' ELSE ',' || SUBSTR(DIGITS(new.y),4,2) END || SUBSTR(nodes,(n+1)*3) , link || ',' || SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(new.y),4, 2) FROM Recurse old , Biconnected new , TABLE (SELECT MAX(n) FROM OrderedNumber odn WHERE
LOCATE(SUBSTR(DIGITS(new.x),4,2)||SUBSTR(DIGITS(ne w.y),4,2),link) = 0 AND (CASE WHEN n < (LENGTH(nodes)+1)/3 THEN SMALLINT(SUBSTR(nodes,n*3+1,2)) ELSE 99 END) <= new.y ) p(n) WHERE seq < 100 AND old.y = new.x AND p.n IS NOT NULL ) , ContainedNode AS ( SELECT s , nodes , SUBSTR(nodes,n*3+1,2) node , (LENGTH(c.nodes)+1)/3 max_n FROM (SELECT nodes , INT(ROWNUMBER() OVER()) s FROM (SELECT DISTINCT SUBSTR(a.nodes,4) FROM Recurse a ) b(nodes) ) c(nodes, s) , TABLE (SELECT n FROM OrderedNumber d WHERE d.n <= LENGTH(c.nodes)/3 ) e ) SELECT DISTINCT nodes AS Connected_Nodes FROM ContainedNode a WHERE NOT EXISTS (SELECT * FROM ContainedNode c WHERE c.s <> a.s AND c.node = a.node AND c.max_n >= a.max_n ) ORDER BY Connected_Nodes ; -------------------------------------------------------------------------
CONNECTED_NODES -------------------- 01,02,03 04,05 06,07,08,09,10
3 record(s) selected.
Hmm. Too much formatting and string manipulations obfuscate your
solution. Here is some attemt (I have to translate from my RDBMS of
choice to db2):
with SymmetricInput as (
select x,y from input
union
select y,x from input
), TransitiveClosure as (
select x,y, '['||x||','||y||')' AS path from input
union all
select tc.x,i.y, path||'-'||'['||i.x||','||i.y||')'
from input i,TransitiveClosure tc
where tc.y=i.x
-- TO DO: the recursion has to cut off the cycles
-- (don't have Graemes DB2 cookbook printout at hand)
), MonotonicPaths as (
select x,y, '['||x||','||y||')' AS path from TransitiveClosure
where x<y
union all
select tc.x,i.y, path||'-'||'['||i.x||','||i.y||')'
from TransitiveClosure i,MonotonicPaths tc
where tc.y=i.x and i.x<i.y
-- Monotonic paths are acyclic
) select distinct path from MonotonicPaths
where x not in (
select x from MonotonicPaths oo where
length(oo.path)>length(o.path)
) and y not in (
select y from MonotonicPaths oo where
length(oo.path)>length(o.path)
);
You are right.
One of my poor design may be to define data type as number(SMALLINT).
So, I need many conversion from number to char.
Another issue would be that I used two near same information(nodes
column information is contained in link column).
Instead of following the chains, how about working backwards COUNTing
rows that are not part of EXISTSing rows?
Assuming Y will always be more than X:
DECLARE GLOBAL TEMPORARY TABLE Connected (X SMALLINT, Y SMALLINT)
INSERT INTO SESSION.Connected VALUES (1, 2), (2, 3), (3, 1), (4, 5),
(6, 8), (7, 8), (8, 9), (8, 10), (9, 10)
SELECT \
COUNT(*) \
FROM \
SESSION.Connected Outer \
WHERE \
NOT EXISTS \
( \
SELECT \
* \
FROM \
SESSION.Connected Inner \
WHERE \
Inner.Y = Outer.X \
AND Inner.Y > Inner.X \
)
Or
SELECT \
COUNT(*) \
FROM \
( \
SELECT \
X \
FROM \
SESSION.Connected \
EXCEPT \
SELECT \
Y \
FROM \
SESSION.Connected \
WHERE \
Y > X
) A
B.
Try
(1,2)
(1,3)
Your first query returns 2. In general, it is very suspicious that you
can do graph queries with plain (non recursive) SQL.
Brian Tkatch wrote: Instead of following the chains, how about working backwards COUNTing rows that are not part of EXISTSing rows?
Assuming Y will always be more than X:
DECLARE GLOBAL TEMPORARY TABLE Connected (X SMALLINT, Y SMALLINT) INSERT INTO SESSION.Connected VALUES (1, 2), (2, 3), (3, 1), (4, 5), (6, 8), (7, 8), (8, 9), (8, 10), (9, 10)
SELECT \ COUNT(*) \ FROM \ SESSION.Connected Outer \ WHERE \ NOT EXISTS \ ( \ SELECT \ * \ FROM \ SESSION.Connected Inner \ WHERE \ Inner.Y = Outer.X \ AND Inner.Y > Inner.X \ )
Or
SELECT \ COUNT(*) \ FROM \ ( \ SELECT \ X \ FROM \ SESSION.Connected \ EXCEPT \ SELECT \ Y \ FROM \ SESSION.Connected \ WHERE \ Y > X ) A
B.
Actually, i have no idea what a graph query is. I was just looking at
the lists for chains as you provided in the original message.
I guess i misunderstood.
B.
Brian Tkatch wrote: Actually, i have no idea what a graph query is.
"Graph query" is a sloppy name for a "query on a graph structure". A
typical graph query is finding transitive closure. It is will known
that graph queries such as transitive closure can't be answered with
standard SQL means -- you have to use recursive SQL. I can't prove the
same for the number of connected components, though; this is why I was
"suspicious" rather than "sure".
Ah, ok, thanx.
I was just trying a different approach, that is, looking for breaks
rather than chains.
B. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Ravi Shankar |
last post by:
Hi all,
I have a calendar application( like Microsoft Outlook) writtn in
Java.Whenever an event is created, we can set SMS/EMAIL notification. Hence
when an event is created, I am storing that...
|
by: Greg |
last post by:
I am working on a project that will have about 500,000 records in an XML
document. This document will need to be queried with XPath, and records
will need to be updated. I was thinking about...
|
by: Shane |
last post by:
I wonder if someone has any ideas about the following.
I am currently producing some reports for a manufacturing company who work
with metal.
A finished part can contain multiple sub-parts to...
|
by: Darren |
last post by:
I have a solution that has a number of projects. Each project
generates a component and each component depends on a number of other
components. What is the best way of managing this dependency so...
|
by: Steve Le Monnier |
last post by:
The ADO.NET DataSet is idea for application development, especially if you
need disconnected data. DataReader objects are great in the connected
environment but are forward only. What do you do...
|
by: roiavidan |
last post by:
Hi,
I'm having a bit of a problem with a small application I wrote in C#,
which uses an Access database (mdb file) for storing financial data.
After looking for a similiar topic and failing to...
|
by: alingsjtu |
last post by:
Hello, every body.
When execute dynamic generated multiple OPENQUERY statements (which
linkes to DB2) in SQLServer, I always got SQL1040N The maximum number
of applications is already connected...
|
by: Vikrant Pendurkar |
last post by:
When i tried to access my application its gives me below error.
Microsoft OLE DB Provider for Oracle error '80004005'
Oracle client and networking components were not found. These components...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
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...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
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)...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
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...
| |