2018-03-08

Finding shortest path in lenght from a hierarchy

Using an analytical function to find out when to stop browsing a hierarchy. Here is an example without further explanation what is happening.
with tre as (
select 0 parent, 1 child, 1 len from dual union all
select 1 parent, 2 child, 2 len from dual union all
select 2 parent, 3 child, 3 len from dual union all
select 3 parent, 1 child, 4 len from dual union all
select 3 parent, 4 child, 5 len from dual union all
select 4 parent, 5 child, 6 len from dual union all
select 5 parent, 6 child, 7 len from dual union all
select 2 parent, 5 child, 20 len from dual
), rcte( root, parent, child, len, lvl, foundpth, pthlen, minpthlen, pth) as (
select t.parent
     , t.parent
     , t.child
     , t.len
     , 1 lvl
     , case when t.child = :endnode then 1 else 0 end foundpth
     , t.len pthlen
     , case when t.child = :endnode then t.len else 9999999 end minpthlen
     , t.parent||'-'||t.child pth
  from tre t
 where t.parent = :startnode
union all
select r.root
     , t.parent
     , t.child
     , t.len
     , r.lvl+1 lvl
     , case when t.child = :endnode then 1 else 0 end
     , r.pthlen+t.len pthlen
     , min(case when t.child = :endnode then r.pthlen+t.len else 9999999 end)over() minpthlen
     , r.pth||'-'||t.child pth
  from tre t, rcte r
 where t.parent = r.child 
   and r.pthlen + t.len < r.minpthlen 
  ) search breadth first by parent,child set ordr
    cycle parent,child set cycle to 1 default 0
select *
  from rcte
 where foundpth = 1
 order by minpthlen, lvl, pth 
 fetch first row only
;

No comments:

Post a Comment

About Me

My photo
I am Timo Raitalaakso. I have been working since 2001 at Solita Oy as a Senior Database Specialist. My main focus is on projects involving Oracle database. Oracle ACE alumni 2012-2018. In this Rafu on db blog I write some interesting issues that evolves from my interaction with databases. Mainly Oracle.