Home » SQL & PL/SQL » SQL & PL/SQL » Find the longest path (Oracle 9i R2)
Find the longest path [message #580474] Mon, 25 March 2013 02:57 Go to next message
Amine
Messages: 264
Registered: March 2010
Senior Member

Hi all,
create table test
(
	a	varchar2(10)	,
	b	varchar2(10)
)
/
insert into test values ('A', 'B');
insert into test values ('B', 'C');
insert into test values ('C', 'D');
insert into test values ('D', 'E');
-- ---------
insert into test values ('K', 'L');
insert into test values ('M', 'N');
-- --------
insert into test values ('Q', 'S');
insert into test values ('S', 'Z');


We want to get the path from "A" to "E". In other words, if we start with any value of the column "a" we have to reach the "maximum" value of the column "b".
"maximum" in sense that we don't find the value of "b" in "a".

Example :
---------
E is not found in the column a, so E is the maximum of A.
- N is the maximum of K
- Z is the maximum of Q and the maximum of S

select ...
from ...
where a = 'A' should return E.

Thanks in advance,
Amine
Re: Find the longest path [message #580476 is a reply to message #580474] Mon, 25 March 2013 03:13 Go to previous messageGo to next message
dariyoosh
Messages: 532
Registered: March 2009
Location: Iran / France
Senior Member
Amine wrote on Mon, 25 March 2013 08:57
Hi all,
. . . "maximum" in sense that we don't find the value of "b" in "a" . . .


What if both the start point and end point are in the same column, for example the path between A and C?

What if that the end point comes right after the start point, for example the path between A and B?


Regards,
Dariyoosh
Re: Find the longest path [message #580477 is a reply to message #580474] Mon, 25 March 2013 03:14 Go to previous messageGo to next message
Michel Cadot
Messages: 58847
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Here's a first step:
SQL> select connect_by_root a, b
  2  from test
  3  where connect_by_isleaf = 1
  4  connect by prior b = a
  5  start with a not in (select b from test)
  6  order by 1
  7  /
CONNECT_BY B
---------- ----------
A          E
K          L
M          N
Q          Z

Regards
Michel
Re: Find the longest path [message #580479 is a reply to message #580477] Mon, 25 March 2013 03:54 Go to previous messageGo to next message
Amine
Messages: 264
Registered: March 2010
Senior Member

Thanks Michel for your reply. But your solution doesn't work on 9i R2.

The output should be like this, for every "a" in test :

A	E
B	E
C	E
K	N
M	N
S	Z
S	Z



Re: Find the longest path [message #580480 is a reply to message #580479] Mon, 25 March 2013 04:03 Go to previous messageGo to next message
Michel Cadot
Messages: 58847
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Quote:
K	  N


This result is wrong, it is not in your data.

Regards
Michel
Re: Find the longest path [message #580484 is a reply to message #580480] Mon, 25 March 2013 04:40 Go to previous messageGo to next message
Amine
Messages: 264
Registered: March 2010
Senior Member

Sorry for that !
Here is the right one :
A	E
B	E
C	E
K	L
M	N
Q	Z
S	Z
Re: Find the longest path [message #580493 is a reply to message #580484] Mon, 25 March 2013 07:47 Go to previous messageGo to next message
Michel Cadot
Messages: 58847
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
SQL> select substr(c,1,instr(c,'/')-1) a, substr(c,instr(c,'/',-1)+1) b
  2  from ( select substr(sys_connect_by_path(a,'/')||'/'||b,2) c, level lvl,
  3                max(level) over
  4                  (partition by substr(sys_connect_by_path(a,'/'),
  5                                       1,
  6                                       instr(sys_connect_by_path(a,'/')||'/','/',1,2)-1))
  7                  maxlvl
  8         from test
  9         connect by prior b = a
 10  --       start with a not in (select b from test)
 11       )
 12  where lvl = maxlvl
 13  order by 1
 14  /
A B
- -
A E
B E
C E
D E
K L
M N
Q Z
S Z

Regards
Michel
Re: Find the longest path [message #580601 is a reply to message #580474] Tue, 26 March 2013 02:08 Go to previous messageGo to next message
saipradyumn
Messages: 183
Registered: October 2011
Location: Hyderabad
Senior Member
Hi Michel,

To get the actaul results can we modify your first query as below

SQL> 
SQL>  select connect_by_root a, b
  2     from test
  3    where connect_by_isleaf = 1
  4   connect by prior b = a
  5    start with a = A
  6    order by 1
  7  ;
 
CONNECT_BY_ROOTA B
---------------- ----------
A                E
B                E
C                E
D                E
K                L
M                N
Q                Z
S                Z
 
8 rows selected
 
SQL> 


Please let me know if I am wrong

Thanks
SaiPradyumn
Re: Find the longest path [message #580607 is a reply to message #580601] Tue, 26 March 2013 02:28 Go to previous messageGo to next message
Michel Cadot
Messages: 58847
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
No, you cannot as the functions you (and I) used don't exist in 9i.
If you want to do it in 10G and up, just remove the START WITH clause in the first query I gave.

Regards
Michel
Re: Find the longest path [message #580611 is a reply to message #580601] Tue, 26 March 2013 02:44 Go to previous messageGo to next message
saipradyumn
Messages: 183
Registered: October 2011
Location: Hyderabad
Senior Member
Thanks Michel
Re: Find the longest path [message #581083 is a reply to message #580611] Mon, 01 April 2013 14:26 Go to previous messageGo to next message
Amine
Messages: 264
Registered: March 2010
Senior Member

Hi all,
I had to do some gymnastic to reach your result.

SQL> select * from v$version;

BANNER                                                                          
----------------------------------------------------------------                
Oracle9i Enterprise Edition Release 9.2.0.8.0 - Production                      
PL/SQL Release 9.2.0.8.0 - Production                                           
CORE	9.2.0.8.0	Production                                                       
TNS for 32-bit Windows: Version 9.2.0.8.0 - Production                          
NLSRTL Version 9.2.0.8.0 - Production                                           

SQL> 
SQL> column c format A10
SQL> column root format A10
SQL> column a format A1
SQL> column b format A1
SQL> column lvl format 9
SQL> column maxlvl format 9
SQL> 
SQL> select
  2  substr(c,1,instr(c,'/')-1) a
  3  , substr(c,instr(c,'/',-1)+1) b
  4  from
  5  (
  6   select substr(sys_connect_by_path(a,'/')||'/'||b,2) c
  7   , level lvl
  8   , max(level) over (partition by substr(sys_connect_by_path(a,'/'),1,instr(sys_connect_by_path(a,'/')||'/','/',1,2)-1)) maxlvl
  9   from test
 10   connect by prior b = a
 11   --       start with a not in (select b from test)
 12  )
 13  where 1 = 1
 14  and lvl = maxlvl
 15  order by 1
 16  /

A B                                                                             
- -                                                                             
  E                                                                             
  E                                                                             
  E                                                                             
  E                                                                             
  L                                                                             
  N                                                                             
  Z                                                                             
  Z 


When I comment the analytic function (max(level)), the query returns this :

SQL> select
  2  substr(c,1,instr(c,'/')-1) a
  3  , substr(c,instr(c,'/',-1)+1) b
  4  from
  5  (
  6   select substr(sys_connect_by_path(a,'/')||'/'||b,2) c
  7   , level lvl
  8   --, max(level) over (partition by substr(sys_connect_by_path(a,'/'),1,instr(sys_connect_by_path(a,'/')||'/','/',1,2)-1)) maxlvl
  9   from test
 10   connect by prior b = a
 11   --       start with a not in (select b from test)
 12  )
 13  where 1 = 1
 14  --and lvl = maxlvl
 15  order by 1
 16  /

A B                                                                             
- -                                                                             
A B                                                                             
A C                                                                             
A D                                                                             
A E                                                                             
B C                                                                             
B D                                                                             
B E                                                                             
C D                                                                             
C E                                                                             
D E                                                                             
K L                                                                             

A B                                                                             
- -                                                                             
M N                                                                             
Q S                                                                             
Q Z                                                                             
S Z        


So, I had to do this to reach the desired output :

SQL> with my_view as
  2  (
  3   select
  4   substr(sys_connect_by_path(a,'/')||'/'||b,2) c
  5   , substr(sys_connect_by_path(a,'/'),1,instr(sys_connect_by_path(a,'/')||'/','/',1,2)-1) root
  6   , level lvl
  7   --, max(level) over (partition by substr(sys_connect_by_path(a,'/'),1,instr(sys_connect_by_path(a,'/')||'/','/',1,2)-1)) maxlvl
  8   from test
  9   connect by prior b = a
 10  )
 11  select
 12  substr(c,1,instr(c,'/')-1) a
 13  , substr(c,instr(c,'/',-1)+1) b
 14  from my_view a
 15  where 1 = 1
 16  and lvl in (select max(lvl) from my_view where root = a.root)
 17  /

A B                                                                             
- -                                                                             
A E                                                                             
B E                                                                             
C E                                                                             
D E                                                                             
K L                                                                             
M N                                                                             
Q Z                                                                             
S Z      


I think it's an implementation issue like it's the case with UTL_FILE.put_line in Oracle 9i.

Regards,
Amine
Re: Find the longest path [message #581084 is a reply to message #581083] Mon, 01 April 2013 14:40 Go to previous message
Michel Cadot
Messages: 58847
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Your not formatted query are unreadable.
It seems there is a bug in 9.2.0.8.
Here's a workaround:
SQL> select substr(c,1,instr(c,'/')-1) a, substr(c,instr(c,'/',-1)+1) b
  2  from ( select c, lvl,
  3                max(lvl) over (partition by substr(c, 1, instr(c||'/','/')-1)) maxlvl
  4         from ( select substr(sys_connect_by_path(a,'/')||'/'||b,2) c, level lvl
  5                from test
  6                connect by prior b = a
  7  --              start with a not in (select b from test)
  8              )
  9       )
 10  where lvl = maxlvl
 11  order by 1
 12  /
A          B
---------- ----------
A          E
B          E
C          E
D          E
K          L
M          N
Q          Z
S          Z

Regards
Michel



Regards
Michel
Previous Topic: Measure time overlap between 3 date ranges
Next Topic: create a local report
Goto Forum:
  


Current Time: Wed Aug 20 10:36:55 CDT 2014

Total time taken to generate the page: 0.09630 seconds