図でイメージするOracleのSQL全集の元原稿
第8回 PivotとUnPivot
第6回 階層問い合わせ
第7回 再帰with句
連載のテーマ
前回と同じとなります。
動作確認環境
Oracle Database 11g Release 11.2.0.1.0 (Windows 32ビット版)
11 枝切り(ノード数の総合計)のみ、
Oracle Database 11g Express Edition Release 11.2.0.2.0 (Windows 32ビット版)
今回のテーマ
今回は、下記の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句
目次
1 with句とは
インラインビューを作成
with句は、select文において、インラインビューを作成するという用途で使われます。
with句は、再帰のないwith句と、再帰のあるwith句(再帰with句)があります。
再帰のないwith句は、Oracle9iから使用可能で、
再帰with句は、Oracle11gR2から使用可能です。
階層問い合わせに関する知識があると、再帰with句を理解しやすいです。
参考リソース
図でイメージするOracleのSQL全集 第6回 階層問い合わせ
2 再帰のないwith句
SQLの可読性の向上
再帰のないwith句の主な使い道は、3つあります。
1つは、テスト用の仮想テーブルの作成です。
-- テスト用の仮想テーブルの作成
with work(Val1,Val2) 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(Val2) 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;
3 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句の再帰項に相当すると考えると理解しやすいです。
4 再帰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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。
5 木構造なデータの探索
親子条件を満たす行を再帰的に出力
再帰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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。
6 有向グラフの探索
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句のイメージは、下記となります。
赤色のバツ印で、親子関係があるけど経路上で訪問済であるノードへの再訪問を検知してます。
7 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を採番する。
8 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を採番する。
9 枝切り(レベル制限)
再帰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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。
10 枝切り(外部結合後の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のイメージは下記となります。
再帰項による木のノードの作成をイメージしてます。
11 枝切り(ノード数の総合計)
分析関数の結果を使った枝切り
再帰項の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関数を使って、
そのレベルのノード数を求めつつ、足し算でノード数の総合計を求め、
枝切り条件として使用してます。
12 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関数を文字列の連結で模倣してます。
13 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演算子を木の根のノードの値を使うことで模倣してます。
14 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で探索を行った結果に対して、深さ優先探索順で連番を付与し、
その連番をソートキーとして使用してます。
15 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関数のソートキーとして使用し、
深さ優先探索順での次の訪問で、レベルがインクリメントされたら、木の葉ではないと判定してます。
16 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句を使って、閉路を考慮した探索を行ってます。
17 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述語を使用して、
同じ木で親子条件を満たして、かつ、訪問済なノードが存在するかを判定してます。
18 ナップサック問題
再帰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の最大値を求めてます。
19 数独
再帰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で数独を解く
参考リソース