10-345 再帰with句で外部結合後のWhere句で枝切り

SQLパズル

hist_table
Grp  ID  KoID
---  --  ----
A    10   100
A    20  null
A    30    40
A    40    50
A    50  null
B    10   100
B    20  null

IDからKoIDまでの経路のIDを、
レベルに応じたインデントを行って、深さ優先探索順で表示する。

出力結果
Grp  Path
---  ------------
A      10
A         100
A      20
A      30
A          40
A              50
B      10
B         100
B      20

こちらを参考にさせていただきました(英語)

データ作成スクリプト

create table hist_table(grp,ID,KoID) as
select 'A',10, 100 from dual union all
select 'A',20,null from dual union all
select 'A',30,  40 from dual union all
select 'A',40,  50 from dual union all
select 'A',50,null from dual union all
select 'B',10, 100 from dual union all
select 'B',20,null from dual;

SQL

--■■■再帰with句を使う方法(11gR2以降)■■■
col Path for a30

with rec(grp,ID,KoID,LV) as(
select grp,ID,KoID,1
  from hist_table a
 where not exists(select 1 from hist_table b
                   where b.grp=a.grp
                     and b.KoID=a.ID)
union all
select a.grp,a.KoID,b.KoID,a.LV+1
  from rec a Left Join hist_table b
    on a.grp  = b.grp
   and a.KoID = b.ID
 where a.KoID is not null)
SEARCH DEPTH FIRST BY grp,ID SET rn
select grp,LPad(to_char(ID),LV*4) as Path
  from rec order by rn;

--■■■階層問い合わせを使う方法■■■
with tmp as(
select grp,ID,KoID
  from hist_table
union all
select grp,KoID,null
  from hist_table a
 where KoID is not null
   and not exists(select 1 from hist_table b
                   where b.grp=a.grp
                     and b.ID=a.KoID))
select grp,LPad(to_char(ID),Level*4) as Path
  from tmp a
start with not exists(select 1 from tmp b
                       where b.grp=a.grp
                         and b.KoID=a.ID)
connect by prior grp = grp
       and prior KoID = ID
order by siblings by grp,ID;

解説

再帰with句では、外部結合後のWhere句で枝切りを行ってます。
PostgreSQLの再帰SQLの使用例 「8. 枝切り(外部結合後のwhere句)」