X

A blog about Oracle Technology Network Japan

  • February 18, 2012

図でイメージするOracle DatabaseのSQL全集 第7回 再帰with句

Guest Author

図でイメージするOracle DatabaseのSQL全集 indexページ▶▶

 


Oracle SQLの各機能をイメージ図を交えて解説

Oracle ACE
山岸 賢治(やまぎし けんじ)ACE

SQLの初心者から上級者までを広く対象読者として、Oracle SQLの各機能の典型的な使用例を、学習効率が高いと思われる順序で、SQLのイメージ図を交えて解説します。
SQLをイメージつきで理解することで、素早くイメージからSQLを考えられるようになることを目標とします。

 

目次

第1部 再帰with句の使用例

第2部 データの探索

第3部 枝切り

第4部 階層問い合わせの機能を模倣

第5部 バックトラック問題

 

今回のテーマ

今回は、下記のOracleのSQL文の評価順序においての、1番目のfrom句でのインラインビューに相当する、with句の使用例と、私のSQLのイメージを解説します。

1番目 from句
2番目 where句 (結合条件)
3番目 start with句
4番目 connect by句
5番目 where句 (行のフィルタ条件)
6番目 group by句
7番目 having句
8番目 model句
9番目 select句
10番目 union、minus、intersectなどの集合演算
11番目 order by句

 

動作確認環境


Oracle Database 11g Release 11.2.0.1.0 (windows 32ビット版)

枝切り(ノード数の総合計)
のみ、 Oracle Database 11g Express Edition Release 11.2.0.2.0 (windows 32ビット版)

 

with句とは

 

インラインビューを作成


with句は、select文において、インラインビューを作成するという用途で使われます。

with句は、再帰のないwith句と、再帰のあるwith句(再帰with句)があります。
再帰のないwith句は、Oracle9iから使用可能で、再帰with句は、Oracle11gR2から使用可能です。

階層問い合わせに関する知識があると、再帰with句を理解しやすいです。

参考リソース
図でイメージするOracleのSQL全集 第6回 階層問い合わせ

 

再帰のないwith句

 

SQLの可読性の向上


再帰のないwith句の主な使い道は、3つあります。
1つは、テスト用の仮想テーブルの作成です。

-- テスト用の仮想テーブルの作成
with work(Val1,Va2) as(
select 1,8 from dual union all
select 2,9 from dual union all
select 6,1 from dual)
select sum(Val1) as sumVal1,
sum(Va2) as sumVal2
  from work;
出力結果
sumVal1  sumVal2
-------  -------
      9       18

2つは、select文の結果を自己結合などで複数回使いたい時の2度書き防止です。
津島博士も、パフォーマンス講座 第11回 良いSQLについて(2)で紹介されてますね。

create table NonRecWithSample(ID,Val) as
select 'AAA',1 from dual union all
select 'AAA',3 from dual union all
select 'BBB',5 from dual union all
select 'CCC',1 from dual union all
select 'DDD',2 from dual union all
select 'DDD',7 from dual;
-- select文の2度書き防止
with tmp as(
select ID,sum(Val) as sumVal
  from NonRecWithSample
group by ID)
select a.ID as a_ID,a.sumVal as a_SumVal,
b.ID as b_ID,b.sumVal as b_SumVal
  from tmp a Join tmp b
    on a.ID < b.ID
   and a.sumVal < b.sumVal
order by a_ID,b_ID;
出力結果
a_ID  a_SumVal  b_ID  b_SumVal
----  --------  ----  --------
AAA          4  BBB          5
AAA          4  DDD          9
BBB          5  DDD          9
CCC          1  DDD          9

3つは、インラインビューを含むSQLを、上から下に読めるようにすることによる、可読性の向上です。

-- インラインビューを含むSQL
select ID,Val
from (select ID,Val,
      count(*) over(partition by ID) as cnt
      from NonRecWithSample)
where cnt=1;
-- 上から下に読めるようにしたSQL
with tmp as(
select ID,Val,
count(*) over(partition by ID) as cnt
  from NonRecWithSample)
select ID,Val
  from tmp
 where cnt=1;

 

1から5までの整数を出力

 

基本的な再帰with句の使用例


再帰with句を使って、1から5までの整数を出力してみます。

-- 1から5までの整数を出力
with rec(Val) as(
select 1 from dual
union all
select Val+1
  from rec
 where Val+1 <= 5)
select Val from rec;
出力結果
Val
---
  1
  2
  3
  4
  5

再帰with句では、union allの上を非再帰項と呼び、union allの下を再帰項と呼びます。

再帰with句は、最初に非再帰項のselect文を実行して、
そのselect文の結果を使って再帰項のselect文を実行して、
そのselect文の結果を使って再帰項のselect文を実行して、
そのselect文の結果を使って再帰項のselect文を実行して、(以下続く・・・)
といった処理を、再帰項のselect文の結果が0件になるまで行います。

上記のSQLでは、最初に、非再帰項のselect 1 from dualで1行作成してます。
次に再帰項において、select句のVal+1とwhere句のVal+1 <= 5で
2から5までの整数を持つ行を作成してます。

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

非再帰項の段階のイメージ

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

再帰項の段階のイメージ

再帰with句の処理をイメージする際には、非再帰項と再帰項で2段階に分けてイメージすると分かりやすいです。
また、階層問い合わせのstart with句が、再帰with句の非再帰項に相当し、階層問い合わせのconnect by句が、再帰with句の再帰項に相当すると考えると理解しやすいです。

 

再帰with句で行の分割

 

1行を複数行に分割


再帰with句で1行を複数行に分割してみます。

create table RowToRows(ID,FromVal,ToVal) as
select 'AA',2,4 from dual union all
select 'BB',8,9 from dual union all
select 'CC',3,5 from dual;

IDごとに、FromValからToValまでの整数の行を作成します。

-- 1行を複数行に分割
with rec(ID,FromVal,ToVal) as(
select ID,FromVal,ToVal
  from RowToRows
union all
select ID,FromVal+1,ToVal
  from rec
 where FromVal+1 <= ToVal)
select ID,FromVal as Val from rec
order by ID,Val;
出力結果
ID  Val
--  ---
AA    2
AA    3
AA    4
BB    8
BB    9
CC    3
CC    4
CC    5

再帰項でToValを上限として数値の加算を行って、行を再帰的に作成してます。

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

非再帰項の段階のイメージ

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

再帰項の段階のイメージ

 

木構造なデータの探索

 

親子条件を満たす行を再帰的に出力


再帰with句で木構造なデータの探索を行うことができます。

create table TreeData(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   1 from dual union all
select  4,   2 from dual union all
select  5,   3 from dual union all
select 10,null from dual union all
select 11,  10 from dual union all
select 12,  10 from dual;

木の根となる条件を、OyaID is null
親子条件を、親のID = 子のOyaID として木構造なデータを探索します。
根からの経路や、各ノードのレベルも求めます。

-- 木構造なデータの探索
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,to_char(ID)
  from TreeData
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,TreeData b
 where a.ID = b.OyaID)
select * from rec;
出力結果
ID  OyaID  LV  Path
--  -----  --  -----
 1   null   1  1
10   null   1  10
 2      1   2  1,2
 3      1   2  1,3
11     10   2  10,11
12     10   2  10,12
 4      2   3  1,2,4
 5      3   3  1,3,5

非再帰項で、OyaIDがnullの行を木の根として出力して、再帰項で、親子条件である、親のID = 子のOyaID を満たす行を再帰的に出力してます。

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

非再帰項の段階のイメージ

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

再帰項の段階のイメージ

 

有向グラフの探索

 

cycle句で閉路の検知


再帰with句で有向グラフの探索を行うことができます。

create table GraphData(ID primary key,NextID) as
select  1,   2 from dual union all
select  2,   3 from dual union all
select  3,null from dual union all
select 50,  51 from dual union all
select 51,  52 from dual union all
select 52,  50 from dual;

木の根となる条件を、ID = 1
親子条件を、親のNextID = 子のID
として訪問可能なノードを出力します。

-- 再帰with句で閉路のない探索
with rec(ID,NextID,LV,Path) as(
select ID,NextID,1,to_char(ID)
  from GraphData
 where ID = 1
union all
select b.ID,b.NextID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,GraphData b
 where a.NextID = b.ID)
select * from rec;
出力結果
ID  NextID  LV  Path
--  ------  --  -----
 1       2   1  1
 2       3   2  1,2
 3    null   3  1,2,3

次は、木の根となる条件を、ID = 50
親子条件を、親のNextID = 子のID
として訪問可能なノードを出力します。

-- 再帰with句で閉路のある探索1
with rec(ID,NextID,LV,Path) as(
select ID,NextID,1,to_char(ID)
  from GraphData
 where ID = 50
union all
select b.ID,b.NextID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,GraphData b
 where a.NextID = b.ID)
select * from rec;
出力結果
ERROR: ORA-32044: 再帰的WITH問合せの実行中にサイクルが検出されました

非再帰項のwhere ID = 50によって、ID=50の行を根とした探索が行われますが、
ID=50の行の子供が、ID=51の行。
ID=51の行の子供が、ID=52の行。
ID=52の行の子供が、ID=50の行。
といったデータになっていて、経路上で訪問済であるノードへの再訪問が行われるため、ORA-32044が発生してしまいます。

このように閉路のあるデータ構造の時には、cycle句を使うと、親子関係があるけど経路上で訪問済であるノードへの再訪問を考慮した探索を行うことができます。

-- 再帰with句で閉路のある探索2
with rec(ID,NextID,LV,Path) as(
select ID,NextID,1,to_char(ID)
  from GraphData
 where ID = 50
union all
select b.ID,b.NextID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,GraphData b
 where a.NextID = b.ID)
cycle ID set IsLoop to 'Y' default 'N'
select * from rec;
出力結果
ID  NextID  LV  Path         IsLoop
--  ------  --  -----------  ------
50      51   1  50           N
51      52   2  50,51        N
52      50   3  50,51,52     N
50      51   4  50,51,52,50  Y

cycle ID set IsLoop to 'Y' default 'N' によって、子ノードとID列が一致する訪問済ノードが存在しなければ、子ノードのIsLoop列にNをセットし、そのノードからの探索を継続します。
子ノードとID列が一致する訪問済ノードが存在したら、cycleが存在すると判定して、子ノードのIsLoop列にYをセットし、そのノードからの探索を打ち切ります。

cycle句のイメージは、下記となります。
赤色のバツ印で、親子関係があるけど経路上で訪問済であるノードへの再訪問を検知してます。

cycle句のイメージ

 

search句 (深さ優先探索)

 

深さ優先探索順で連番を付与


create table HukasaT(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   1 from dual union all
select  4,   1 from dual union all
select  5,   3 from dual union all
select  6,   3 from dual union all
select  7,   4 from dual union all
select  8,   4 from dual union all
select  9,   6 from dual union all
select 10,   7 from dual union all
select 20,null from dual union all
select 21,  20 from dual union all
select 22,  20 from dual union all
select 23,  21 from dual union all
select 24,  21 from dual;

search句を使って、再帰withで探索を行った結果に対し、深さ優先探索順で連番を付与できます。

-- 深さ優先探索順で連番を付与
with rec(treeID,ID,OyaID,LV,Path) as(
select ID,ID,OyaID,1,to_char(ID)
  from HukasaT
 where OyaID is null
union all
select a.treeID,b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,HukasaT b
 where a.ID = b.OyaID)
search depth first by ID desc set rn
select rn,treeID,ID,OyaID,LV,Path
  from rec
order by rn;
出力結果
rn  treeID  ID  OyaID  LV  Path
--  ------  --  -----  --  --------
 1      20  20   null   1  20
 2      20  22     20   2  20,22
 3      20  21     20   2  20,21
 4      20  24     21   3  20,21,24
 5      20  23     21   3  20,21,23
 6       1   1   null   1  1
 7       1   4      1   2  1,4
 8       1   8      4   3  1,4,8
 9       1   7      4   3  1,4,7
10       1  10      7   4  1,4,7,10
11       1   3      1   2  1,3
12       1   6      3   3  1,3,6
13       1   9      6   4  1,3,6,9
14       1   5      3   3  1,3,5
15       1   2      1   2  1,2

search depth first by ID desc set rnを指定してますので、下記の順序でrnが採番されます。

再帰with句の非再帰項で木の根を選ぶ段階で、IDの大きいほうから選ばれる。
根からの深さ優先探索でも、子供が複数あったらIDの大きいほうから選ばれる。
そして深さ優先探索の行きがけ順でrnを採番する。

 

search句 (幅優先探索)

 

幅優先探索順で連番を付与


create table HabaT(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   1 from dual union all
select  7,   2 from dual union all
select  8,   2 from dual union all
select  9,   8 from dual union all
select  5,   3 from dual union all
select  6,   3 from dual union all
select 30,null from dual union all
select 31,  30 from dual;

search句を使って、再帰withで探索を行った結果に対し、幅優先探索順で連番を付与できます。

-- 幅優先探索順で連番を付与
with rec(treeID,ID,OyaID,LV,Path) as(
select ID,ID,OyaID,1,to_char(ID)
  from HabaT
 where OyaID is null
union all
select a.treeID,b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,HabaT b
 where a.ID = b.OyaID)
search breadth first by ID desc set rn
select rn,treeID,ID,OyaID,LV,Path
  from rec
order by rn;
出力結果
rn  treeID  ID  OyaID  LV  Path
--  ------  --  -----  --  -------
 1      30  30   null   1  30
 2       1   1   null   1  1
 3      30  31     30   2  30,31
 4       1   3      1   2  1,3
 5       1   2      1   2  1,2
 6       1   8      2   3  1,2,8
 7       1   7      2   3  1,2,7
 8       1   6      3   3  1,3,6
 9       1   5      3   3  1,3,5
10       1   9      8   4  1,2,8,9

search breadth first by ID desc set rnを指定してますので、下記の順序でrnが採番されます。

レベルが1のノードを選ぶ。複数あったらIDの大きいほうから選ばれる。
レベルが2のノードを選ぶ。複数あったらIDの大きいほうから選ばれる。
レベルが3のノードを選ぶ。複数あったらIDの大きいほうから選ばれる。
レベルが4のノードを選ぶ。複数あったらIDの大きいほうから選ばれる。
そして選択したノードからrnを採番する。

 

枝切り(レベル制限)

 

再帰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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。

再帰項の段階のイメージ

 

枝切り(外部結合後の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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。

再帰項の段階のイメージ

 

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

 

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


再帰項の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関数を使って、そのレベルのノード数を求めつつ、足し算でノード数の総合計を求め、枝切り条件として使用してます。

 

Level擬似列,sys_connect_by_path関数

 

ノードのレベル,根からの経路


create table HierarchicalT(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,   1 from dual union all
select  6,   5 from dual union all
select  7,   2 from dual union all
select 20,null from dual union all
select 21,  20 from dual union all
select 22,  21 from dual;

下記のLevel擬似列,sys_connect_by_path関数を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,OyaID,
Level,sys_connect_by_path(to_char(ID),',') as Path
  from HierarchicalT
start with OyaID is null
connect by prior ID = OyaID;
出力結果
ID  OyaID  Level  Path
--  -----  -----  ---------
 1   null      1  ,1
 2      1      2  ,1,2
 3      2      3  ,1,2,3
 4      3      4  ,1,2,3,4
 7      2      3  ,1,2,7
 5      1      2  ,1,5
 6      5      3  ,1,5,6
20   null      1  ,20
21     20      2  ,20,21
22     21      3  ,20,21,22
-- 再帰with句で模倣
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,',' || to_char(ID)
  from HierarchicalT
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,HierarchicalT b
 where a.ID = b.OyaID)
select * from rec;

Level擬似列を足し算で模倣し、sys_connect_by_path関数を文字列の連結で模倣してます。

 

prior演算子,connect_by_root演算子

 

親ノードの値,根ノードの値


下記のprior演算子,connect_by_root演算子を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,OyaID,prior ID as preID,
connect_by_root ID as rootID,
Level,sys_connect_by_path(to_char(ID),',') as Path
  from HierarchicalT
start with OyaID is null
connect by prior ID = OyaID;
出力結果
ID  OyaID  preID  rootID  Level  Path
--  -----  -----  ------  -----  ---------
 1   null   null       1      1  ,1
 2      1      1       1      2  ,1,2
 3      2      2       1      3  ,1,2,3
 4      3      3       1      4  ,1,2,3,4
 7      2      2       1      3  ,1,2,7
 5      1      1       1      2  ,1,5
 6      5      5       1      3  ,1,5,6
20   null   null      20      1  ,20
21     20     20      20      2  ,20,21
22     21     21      20      3  ,20,21,22
-- 再帰with句で模倣
with rec(ID,OyaID,preID,rootID,LV,Path) as(
select ID,OyaID,to_number(null),ID,1,
',' || to_char(ID)
  from HierarchicalT
 where OyaID is null
union all
select b.ID,b.OyaID,a.ID,a.rootID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,HierarchicalT b
 where a.ID = b.OyaID)
select * from rec;

prior演算子を親ノードの値を使うことで模倣し、connect_by_root演算子を木の根のノードの値を使うことで模倣してます。

 

order siblings by

 

深さ優先探索順で出力


create table siblingsT(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   1 from dual union all
select  4,   1 from dual union all
select  5,   3 from dual union all
select  6,   3 from dual union all
select  7,   4 from dual union all
select  8,   4 from dual union all
select  9,   6 from dual union all
select 10,   7 from dual union all
select 20,null from dual union all
select 21,  20 from dual union all
select 22,  20 from dual union all
select 23,  21 from dual union all
select 24,  21 from dual;

下記のorder siblings byを使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select connect_by_root ID as treeID,
ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path
  from siblingsT
start with OyaID is null
connect by prior ID = OyaID
order siblings by ID desc;
出力結果
treeID  ID  OyaID  Level  Path
------  --  -----  -----  ---------
    20  20   null      1  ,20
    20  22     20      2  ,20,22
    20  21     20      2  ,20,21
    20  24     21      3  ,20,21,24
    20  23     21      3  ,20,21,23
     1   1   null      1  ,1
     1   4      1      2  ,1,4
     1   8      4      3  ,1,4,8
     1   7      4      3  ,1,4,7
     1  10      7      4  ,1,4,7,10
     1   3      1      2  ,1,3
     1   6      3      3  ,1,3,6
     1   9      6      4  ,1,3,6,9
     1   5      3      3  ,1,3,5
     1   2      1      2  ,1,2
-- 再帰with句で模倣
with rec(treeID,ID,OyaID,LV,Path) as(
select ID,ID,OyaID,1,',' || to_char(ID)
  from siblingsT
 where OyaID is null
union all
select a.treeID,b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,siblingsT b
 where a.ID = b.OyaID)
search depth first by ID desc set SortKey
select * from rec order by SortKey;

search句を使って、再帰withで探索を行った結果に対して、深さ優先探索順で連番を付与し、その連番をソートキーとして使用してます。

 

connect_by_IsLeaf擬似列

 

ノードが木の葉かを判定


create table IsLeafT(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,   1 from dual union all
select  6,   5 from dual union all
select  7,   2 from dual union all
select 20,null from dual union all
select 21,  20 from dual union all
select 22,  21 from dual;

下記のconnect_by_IsLeaf擬似列を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path,
connect_by_IsLeaf as IsLeaf
  from IsLeafT
start with OyaID is null
connect by prior ID = OyaID;
出力結果
ID  OyaID  Level  Path       IsLeaf
--  -----  -----  ---------  ------
 1   null      1  ,1         0
 2      1      2  ,1,2       0
 3      2      3  ,1,2,3     0
 4      3      4  ,1,2,3,4   1
 7      2      3  ,1,2,7     1
 5      1      2  ,1,5       0
 6      5      3  ,1,5,6     1
20   null      1  ,20        0
21     20      2  ,20,21     0
22     21      3  ,20,21,22  1
-- 再帰with句で模倣する方法1
-- case式でexists述語を使用
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,',' || to_char(ID)
  from IsLeafT
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,IsLeafT b
 where a.ID = b.OyaID)
select ID,OyaID,LV,Path,
case when exists(select 1 from rec b
                  where a.ID = b.OyaID)
     then 0 else 1 end as IsLeaf
  from rec a;

上記のSQLでは、case式でexists述語を使用して、子ノードが存在するかをチェックして、子ノードが存在すれば木の葉ではないと判定し、子ノードが存在しなければ木の葉であると判定してます。

-- 再帰with句で模倣する方法2
-- 深さ優先探索順でレベルを比較
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,',' || to_char(ID)
  from IsLeafT
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,IsLeafT b
 where a.ID = b.OyaID)
search depth first by ID set SortKey
select ID,OyaID,LV,Path,
case when Lead(LV) over(order by SortKey) > LV
     then 0 else 1 end as IsLeaf
  from rec;

search句を使って、再帰withで探索を行った結果に対して、深さ優先探索順で連番を付与してます。
そして、その連番をLead関数のソートキーとして使用し、深さ優先探索順での次の訪問で、レベルがインクリメントされたら、木の葉ではないと判定してます。

 

connect by NoCycle

 

閉路を考慮した探索


create table NoCycleT(ID primary key,nextID) as
select 1,2 from dual union all
select 2,3 from dual union all
select 3,4 from dual union all
select 4,1 from dual union all
select 5,6 from dual;

下記のconnect by NoCycleを使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,nextID,
sys_connect_by_path(to_char(ID),',') as Path
  from NoCycleT
start with ID = 1
connect by NoCycle prior nextID = ID;
出力結果
ID  nextID  Path
--  ------  --------
 1       2  ,1
 2       3  ,1,2
 3       4  ,1,2,3
 4       1  ,1,2,3,4
-- 再帰with句で模倣
with rec(ID,nextID,Path) as(
select ID,nextID,',' || to_char(ID)
  from NoCycleT
 where ID = 1
union all
select b.ID,b.nextID,
a.Path || ',' || to_char(b.ID)
  from rec a,NoCycleT b
 where a.nextID = b.ID)
cycle ID set IsLoop to 'Y' default 'N'
select ID,nextID,Path
  from rec
 where IsLoop = 'N';

cycle句を使って、閉路を考慮した探索を行ってます。

 

connect_by_IsCycle擬似列

 

訪問済ノードを子供に持つかを判定


下記のconnect_by_IsCycle擬似列を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,nextID,
sys_connect_by_path(to_char(ID),',') as Path,
connect_by_IsCycle as IsCycle
  from NoCycleT
start with ID = 1
connect by NoCycle prior nextID = ID;
出力結果
ID  nextID  Path      IsCycle
--  ------  --------  -------
 1       2  ,1              0
 2       3  ,1,2            0
 3       4  ,1,2,3          0
 4       1  ,1,2,3,4        1
-- 再帰with句で模倣
with rec(TreeID,ID,nextID,Path) as(
select ID,ID,nextID,',' || to_char(ID)
  from noCycleT
 where ID=1
union all
select a.TreeID,b.ID,b.nextID,
a.Path || ',' || to_char(b.ID)
  from rec a,noCycleT b
 where a.nextID = b.ID)
cycle ID set IsLoop to 'Y' default 'N'
select TreeID,ID,nextID,Path,
case when exists(select 1 from rec b
                  where b.IsLoop = 'Y'
                    and a.TreeID = b.TreeID
                    and a.nextID = b.ID)
     then 1 else 0 end as IsCycle
  from rec a
 where IsLoop = 'N';

case式でexists述語を使用して、同じ木で親子条件を満たして、かつ、訪問済なノードが存在するかを判定してます。

 

ナップサック問題

 

再帰with句で組み合わせの列挙


再帰with句で、ナップサック問題を解いてみます。
最大で20kgまでの荷物を持てるとして、Valが最大になるIDの組み合わせを求めます。

create table nimotu(ID primary key,Val,Kg) as
select 1, 7,10 from dual union all
select 2, 2, 4 from dual union all
select 3, 9, 5 from dual union all
select 4, 4, 1 from dual union all
select 5, 9, 7 from dual union all
select 6, 7, 3 from dual union all
select 7, 4, 6 from dual union all
select 8, 5, 3 from dual;
with rec(ID,IDList,sumVal,SumKg) as(
select ID,to_char(ID),Val,Kg
  from nimotu
union all
select b.ID,a.IDList || ',' || to_char(b.ID),
a.sumVal+b.Val,a.SumKg+b.Kg
  from rec a,nimotu b
 where a.ID < b.ID
   and a.SumKg+b.Kg <= 20)
select ID,IDList,sumVal,sumKg
from (select ID,IDList,sumVal,sumKg,
      max(sumVal) over() as maxSumVal
      from rec)
where sumVal = maxSumVal;
出力結果
ID  IDList     sumVal  sumKg
--  ---------  ------  -----
 8  3,4,5,6,8      34     19

再帰with句で20kg以下となる全ての組み合わせを求めてから、分析関数のmax関数でsumValの最大値を求めてます。

 

数独

 

再帰with句で数独を解く


"Oracle Database 11g Release 2に関する10の重要なこと - askTom Live -" の
Point4: Recursive Subquery Factoring 【再帰的副問合せのファクタリング】を意識しながら、再帰with句で数独を解いてみます。

with rec(LV,Val) as(
select 1,'530070000'
      || '600195000'
      || '098000060'
      || '800060003'
      || '400803001'
      || '700020006'
      || '060000280'
      || '000419005'
      || '000080079' from dual
union all
select LV+1,
case when substr(Val,LV,1) = '0'
     then substr(Val,1,LV-1) || to_char(cnt)
       || substr(Val,LV+1) else Val end
from rec a,(select RowNum as cnt from dict where RowNum <= 9) b
where LV <= 81
  and (substr(Val,LV,1) = '0' or cnt=1)
  and (substr(Val,LV,1) !='0'
    or (instr(substr(Val,trunc((LV-1)/9)*9+1,9),to_char(cnt)) = 0 /*横チェック*/
    and instr(substr(Val,mod(LV-1,9)+1   ,1),to_char(cnt)) = 0 /*縦チェック*/
    and instr(substr(Val,mod(LV-1,9)+1+ 9,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+18,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+27,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+36,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+45,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+54,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+63,1),to_char(cnt)) = 0
    and instr(substr(Val,mod(LV-1,9)+1+72,1),to_char(cnt)) = 0
    /*正方形チェック*/
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)   ,3),to_char(cnt))=0
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)+ 9,3),to_char(cnt))=0
    and instr(substr(Val,trunc(mod(LV-1,9)/3)*3+1+9*(trunc(trunc((LV-1)/9)/3)*3)+18,3),to_char(cnt))=0)))
select Val from rec
where LV = 82;
出力結果
Val
---------------------------------------------------------------------------------
534678912672195348198342567859761423426853791713924856961537284287419635345286179

再帰項で、1から9までの連番のインラインビューとの内部結合を繰り返してます。
結合条件で、その連番でマスを埋めることが可能かをチェックしてます。

 

参考リソース
マニュアル --- substr関数
マニュアル --- instr関数
OracleSQLパズル --- PL/SQLで数独を解く

 

参考リソース

マニュアル --- subquery_factoring_clause
@IT --- 新しい業界標準「SQL99」詳細解説

 

"図でイメージするOracle DatabaseのSQL全集" インデックスに戻る

Copyright © 2012, Oracle Corporation Japan. All rights reserved.
無断転載を禁ず

この文書はあくまでも参考資料であり、掲載されている情報は予告なしに変更されることがあります。日本オラクル社は本書の内容に関していかなる保証もいたしません。また、本書の内容に関連したいかなる損害についても責任を負いかねます。

Oracleは米国Oracle Corporationの登録商標です。文中に参照されている各製品名及びサービス名は米国Oracle Corporationの商標または登録商標です。その他の製品名及びサービス名はそれぞれの所有者の商標または登録商標の可能性があります。

山岸 賢治山岸 賢治(やまぎし けんじ)
Oracle ACEの1人。
OracleSQLパズルの運営者。


ページトップへ戻る▲

 

図でイメージするOracle DatabaseのSQL全集 indexページ▶▶

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.