枝切り(レベル制限)

再帰with句での枝切り

階層問い合わせと同様に、再帰with句でも枝切りを行うことができます。

create table LevelEdaKiri(ID primary key,OyaID) as
select 10,null from dual union all
select 11,  10 from dual union all
select 12,  11 from dual union all
select 13,  12 from dual union all
select 14,  13 from dual union all
select 31,  10 from dual union all
select 32,  31 from dual union all
select 33,  32 from dual;

ID = 10 の行から探索を始めて、到達可能なノードを表示します。
ただし、ノードのレベルを3以下に制限します。

-- レベル制限で枝切り
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,to_char(ID)
  from LevelEdaKiri
 where ID = 10
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,LevelEdaKiri b
 where a.ID = b.OyaID
   and a.LV+1 <= 3)
select * from rec;

出力結果
ID  OyaID  LV  Path
--  -----  --  --------
10   null   1  10
11     10   2  10,11
31     10   2  10,31
12     11   3  10,11,12
32     31   3  10,31,32

上記のSQLのように、再帰項の内部結合のwhere句で条件指定して枝切りを行うことができます。

非再帰項の段階での、SQLのイメージは下記となります。
非再帰項による木の根の作成をイメージしてます。

再帰項の段階での、SQLのイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。

▲ ページTOPに戻る

枝切り(外部結合後のwhere句)

子ノードがなくても行を出力

再帰項での、外部結合後のwhere句で枝切りを行うこともできます。
子ノードがなくても行を出力したい時に使います。

create table OuterJoinEdakiri(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   2 from dual union all
select  4,   3 from dual union all
select  5,   3 from dual union all
select  6,   2 from dual union all
select 80,null from dual union all
select 81,  80 from dual union all
select 82,  80 from dual union all
select 83,  81 from dual union all
select 84,  83 from dual;

OyaID is null の行から探索を始めて、到達可能なノードを表示します。
ただし、ノードのレベルを3以下に制限し、
レベル1で到達可能なノード
レベル2で到達可能なノード(なければnull)
レベル3で到達可能なノード(なければnull)
をそれぞれ表示します。

-- 外部結合後のwhere句で枝切り
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,to_char(ID)
  from OuterJoinEdakiri
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a Left Join OuterJoinEdakiri b
    on a.ID = b.OyaID
 where a.LV+1 <= 3)
select * from rec order by Path;

出力結果
  ID  OyaID  LV  Path
----  -----  --  --------
   1   null   1  1
   2      1   2  1,2
   3      2   3  1,2,3
   6      2   3  1,2,6
  80   null   1  80
  81     80   2  80,81
  83     81   3  80,81,83
  82     80   2  80,82
null   null   3  80,82,

非再帰項の段階での、SQLのイメージは下記となります。
非再帰項による木の根の作成をイメージしてます。

再帰項の段階での、SQLのイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。

▲ ページTOPに戻る

枝切り(ノード数の総合計)

分析関数の結果を使った枝切り

再帰項のselect句での分析関数の結果を使って、枝切りを行うこともできます。

create table NodeCntEdakiri(ID) as
select RowNum from dict where RowNum <= 10;

IDが3以下の行を木の根として、
親子条件を (親の行の)ID + 1 = (子の行の)ID とし、
幅優先探索でのノード数の総合計が10を超えたら、探索を打ち切ってみます。

-- ノード数の総合計で枝切り
with rec(RootID,ID,LV,Path,NodeCnt) as(
select ID,ID,1,to_char(ID),count(*) over()
  from NodeCntEdakiri
 where ID <= 3
union all
select a.RootID,b.ID,a.LV+1,
a.Path || ',' || to_char(b.ID),
a.NodeCnt+count(*) over()
  from rec a,NodeCntEdakiri b
 where a.ID+1 = b.ID
   and a.NodeCnt <= 10)
select * from rec;

出力結果
RootID  ID  LV  Path     NodeCnt
------  --  --  -------  -------
     1   1   1  1              3
     2   2   1  2              3
     3   3   1  3              3
     1   2   2  1,2            6
     2   3   2  2,3            6
     3   4   2  3,4            6
     1   3   3  1,2,3          9
     2   4   3  2,3,4          9
     3   5   3  3,4,5          9
     1   4   4  1,2,3,4       12
     2   5   4  2,3,4,5       12
     3   6   4  3,4,5,6       12

再帰項で分析関数のcount関数を使って、そのレベルのノード数を求めつつ、足し算でノード数の総合計を求め、枝切り条件として使用してます。

▲ ページTOPに戻る

• ＜ 前のページへ
• 1
• 2
• 3
• 4
• 5
• 6
• 次のページへ ＞