木構造なデータの探索
親子条件を満たす行を再帰的に出力
再帰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句のイメージは、下記となります。
赤色のバツ印で、親子関係があるけど経路上で訪問済であるノードへの再訪問を検知してます。
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を採番する。