Home » SQL & PL/SQL » SQL & PL/SQL » CONNECT BY in a graph (10.2.0.3)
CONNECT BY in a graph [message #330065] Fri, 27 June 2008 08:49 Go to next message
_jum
Messages: 508
Registered: February 2008
Senior Member
I have a directed graph and want to find a way through it, independend of the directions of the single leaves.
The example graph is to go from Point 1 to Point 9.
with a as 
(
  select 1 st_pt,2 end_pt from dual
 UNION ALL
  select 2      ,3        from dual
 UNION ALL
  select 4      ,3        from dual
 UNION ALL
  select 4      ,5        from dual
 UNION ALL
  select 6      ,5        from dual
 UNION ALL
  select 7      ,6        from dual
 UNION ALL
  select 7      ,8        from dual
 UNION ALL
  select 8      ,9        from dual
)
select level, st_pt, end_pt, SYS_CONNECT_BY_PATH(st_pt, '/') way
 from a
 start with st_pt=1
 connect by NOCYCLE
  (PRIOR end_pt=st_pt)
   or
  (PRIOR st_pt=end_pt)	
   or
  (PRIOR end_pt=end_pt)	
   or
  (PRIOR st_pt=st_pt)	
 

Tried to use CONNECT BY with all alternatives for the joins (startpoint1=startpoint2, startpoint1=endpoint2,...).
But had only half success, the way through the graph is found but shown with '/1/2/4/4/6/7/7/8' instead of '/1/2/3/4/5/6/7/8/9'.
LEVEL	ST_PT	END_PT	WAY
1	1	2	/1
2	2	3	/1/2
3	4	3	/1/2/4
4	4	5	/1/2/4/4
5	6	5	/1/2/4/4/6
6	7	6	/1/2/4/4/6/7
7	7	8	/1/2/4/4/6/7/7
8	8	9	/1/2/4/4/6/7/7/8

Is there a simple solution in SQL ?
Re: CONNECT BY in a graph [message #330169 is a reply to message #330065] Fri, 27 June 2008 14:48 Go to previous messageGo to next message
rdebruyn
Messages: 17
Registered: June 2008
Location: Ottawa
Junior Member
It may simply a matter of the data in the right format or I may not quite understand what you're looking for. I've changed the data and the connect by clause.
select SYS_CONNECT_BY_PATH(end_pt, '/')
from (
  select null st_pt,1 end_pt from dual
 UNION ALL
  select 1 st_pt,2 end_pt from dual
 UNION ALL
  select 2      ,3        from dual
 UNION ALL
  select 2      ,4        from dual
 UNION ALL
  select 4      ,5        from dual
 UNION ALL
  select 1      ,6        from dual
 UNION ALL
  select 1      ,7        from dual
 UNION ALL
  select 7      ,8        from dual
 UNION ALL
  select 8      ,9        from dual)
start with st_pt is null
connect by prior end_pt = st_pt

Re: CONNECT BY in a graph [message #330391 is a reply to message #330169] Mon, 30 June 2008 01:19 Go to previous messageGo to next message
_jum
Messages: 508
Registered: February 2008
Senior Member
Thanks, this is an extreme simplified example for a utility network table with >1.000.000 nodes.

The water in the example will go from node 1 to node 9 via 1->2->3->4->5->6->7->8->9, though the pipe 4->3 is "built in" in the false direction with startpoint 4 and endpoint 3.

To find the "path" for the water I use CONNECT BY and to find in in all circumstances (combinations of start- and endpoint) I use the ugly (PRIOR ...) OR (PRIOR ...) construct.

My SELECT works, but slow because of the OR and gives as result
/1/2/4/4/6/7/7/8 what is the correct list of startpoints but not the "way" /1/2/3/4/5/6/7/8/9 the water really will flow.

Because of the huge amount of data, it hoped to achieve the result with a single SELECT (no internal copy of the list ?).

Help/hints are very appreciated.

Re: CONNECT BY in a graph [message #330461 is a reply to message #330391] Mon, 30 June 2008 04:10 Go to previous messageGo to next message
rleishman
Messages: 3724
Registered: October 2005
Location: Melbourne, Australia
Senior Member
  1  with a as
  2  (
  3    select 1 st_pt,2 end_pt from dual
  4   UNION ALL
  5    select 2      ,3        from dual
  6   UNION ALL
  7    select 4      ,3        from dual
  8   UNION ALL
  9    select 4      ,5        from dual
 10   UNION ALL
 11    select 6      ,5        from dual
 12   UNION ALL
 13    select 7      ,6        from dual
 14   UNION ALL
 15    select 7      ,8        from dual
 16   UNION ALL
 17    select 8      ,9        from dual
 18  )
 19  select level, st_pt, end_pt, SYS_CONNECT_BY_PATH(st_pt, '/') way
 20   from (select st_pt, end_pt from a union select end_pt, st_pt from a)
 21   start with st_pt=1
 22   connect by NOCYCLE
 23*   (PRIOR end_pt=st_pt)
TMT@ODMSP> /

     LEVEL      ST_PT     END_PT WAY
---------- ---------- ---------- ----------------------------------------
         1          1          2 /1
         2          2          1 /1/2
         2          2          3 /1/2
         3          3          4 /1/2/3
         4          4          5 /1/2/3/4
         5          5          6 /1/2/3/4/5
         6          6          7 /1/2/3/4/5/6
         7          7          8 /1/2/3/4/5/6/7
         8          8          9 /1/2/3/4/5/6/7/8

9 rows selected.


Ross Leishman
Re: CONNECT BY in a graph [message #330496 is a reply to message #330065] Mon, 30 June 2008 05:17 Go to previous messageGo to next message
JRowbottom
Messages: 5933
Registered: June 2006
Location: Sunny North Yorkshire, ho...
Senior Member
If you want Connect by to go up or down connections, the easiest way is to duplicate & reverse the data, so it knows about both directions:
  1  with a as
  2  (
  3    select 1 st_pt,2 end_pt from dual
  4   UNION ALL
  5    select 2      ,3        from dual
  6   UNION ALL
  7    select 4      ,3        from dual
  8   UNION ALL
  9    select 4      ,5        from dual
 10   UNION ALL
 11    select 6      ,5        from dual
 12   UNION ALL
 13    select 7      ,6        from dual
 14   UNION ALL
 15    select 7      ,8        from dual
 16   UNION ALL
 17    select 8      ,9        from dual
 18  )
 19  , b as (select st_pt,end_pt from a
 20          union all
 21          select end_pt,st_pt from a)
 22  select level, st_pt, end_pt, cast(SYS_CONNECT_BY_PATH(st_pt, '/')  as varchar2(30)) way
 23   from b
 24   start with st_pt=1
 25   connect by NOCYCLE (PRIOR end_pt = st_pt)
 26* order by level
SQL> /

     LEVEL      ST_PT     END_PT WAY
---------- ---------- ---------- ------------------------------
         1          1          2 /1
         2          2          3 /1/2
         2          2          1 /1/2
         3          3          4 /1/2/3
         4          4          5 /1/2/3/4
         5          5          6 /1/2/3/4/5
         6          6          7 /1/2/3/4/5/6
         7          7          8 /1/2/3/4/5/6/7
         8          8          9 /1/2/3/4/5/6/7/8

9 rows selected.


You mention that you've got a lot of data - this might pose a problem for you.

[Too slow - that'll teach me to get distracted half way through]

[Updated on: Mon, 30 June 2008 05:19]

Report message to a moderator

Re: CONNECT BY in a graph [message #330529 is a reply to message #330496] Mon, 30 June 2008 06:53 Go to previous message
_jum
Messages: 508
Registered: February 2008
Senior Member
Implemented the solution in test db, worked fine Smile
Needs nearly double bytes and costs double, but is 15% faster than the old query and much "prettier".
Many thanks to @JRowbottom and @rleishman!
Previous Topic: Query Totals with Rollup Question
Next Topic: Check and Process for ATLEAST 1 entry in table
Goto Forum:
  


Current Time: Tue Dec 06 14:32:09 CST 2016

Total time taken to generate the page: 0.07941 seconds