階層問い合わせでの枝切り
無駄な探索を打ち切る
深さ優先探索や幅優先探索において、無駄な探索を打ち切ることを「枝切り」もしくは「枝刈り」といいます。
Oracleの階層問い合わせでは、親子条件を満たす行を繰り返し取得していきますが、
connect by句で条件を指定して、無駄な繰り返しを打ち切る「枝切り」を行うことができます。
Oracleの階層問い合わせで使われる枝切りは、
- Level擬似列を使った枝切り
- 探索終了条件を指定した枝切り
- 上記2つの組み合わせ
となります。
参考リソース
Level擬似列で枝切り
ノードのレベルの制限
create table LevelEdaKiri(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, 2 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 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;
枝切りを行わない、connect by句で親子条件のみを指定した階層問い合わせを実行してみます。
-- connect by句で親子条件のみを指定
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path
from LevelEdaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
order by Path;
出力結果
ID OyaID Level Path
-- ----- ----- ---------------
1 null 1 ,1
2 1 2 ,1,2
3 2 3 ,1,2,3
5 3 4 ,1,2,3,5
6 3 4 ,1,2,3,6
4 2 3 ,1,2,4
7 4 4 ,1,2,4,7
10 null 1 ,10
11 10 2 ,10,11
12 11 3 ,10,11,12
13 12 4 ,10,11,12,13
14 13 5 ,10,11,12,13,14
SQLのイメージは下記となります。木を区切る赤線をイメージしてます。
今度は、Level擬似列で枝切りを行う階層問い合わせを実行します。
親子条件であるprior ID = OyaIDと枝切り条件としてのLevel <= 3
をandでつなげた論理積をconnect by句で指定します。
これにより親子条件を満たしたとしても、Levelが4以上のノードは出力されなくなります。
なお、枝切りでは、枝を切る条件の否定条件をconnect by句に記述する必要があります。
例えば、Levelが8以上のノードを枝切りしたいのであれば、
connect by句には、Level <= 7と記述するか、Not述語を使って、Not(Level >= 8)
といったふうに、枝を切る条件の否定条件を記述する必要があります。
-- Level擬似列で枝切り
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path
from LevelEdaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
and Level <= 3 --枝切り条件
order by Path;
出力結果
ID OyaID Level Path
-- ----- ----- ---------
1 null 1 ,1
2 1 2 ,1,2
3 2 3 ,1,2,3
4 2 3 ,1,2,4
10 null 1 ,10
11 10 2 ,10,11
12 11 3 ,10,11,12
SQLのイメージは下記となります。木を区切る赤線をイメージしてます。
探索終了条件を指定して枝切り
特定値を持つノードを訪問したら探索を打ち切る
create table PriorEdaKiri(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, 2 from dual union all
select 5, 3 from dual union all
select 6, 4 from dual union all
select 50,null from dual union all
select 51, 50 from dual union all
select 52, 51 from dual;
枝切りを行わない、connect by句で親子条件のみを指定した階層問い合わせを実行してみます。
-- connect by句で親子条件のみを指定
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path
from PriorEdaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
order by Path;
出力結果
ID OyaID Level Path
-- ----- ----- ---------
1 null 1 ,1
2 1 2 ,1,2
3 2 3 ,1,2,3
5 3 4 ,1,2,3,5
4 2 3 ,1,2,4
6 4 4 ,1,2,4,6
50 null 1 ,50
51 50 2 ,50,51
52 51 3 ,50,51,52
SQLのイメージは下記となります。木を区切る赤線をイメージしてます。
今度は、探索終了条件を指定して枝切りを行う階層問い合わせを実行します。
親子条件であるprior ID = OyaIDと枝切り条件としてのprior ID not in(2,51)
をandでつなげた論理積をconnect by句で指定します。
これにより親子条件を満たしたとしても、親ノードのIDが2または51であるノードとその子孫は出力されなくなります。
-- 探索終了条件を指定して枝切り
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path
from PriorEdaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
and prior ID not in(2,51) --枝切り条件
order by Path;
出力結果
ID OyaID Level Path
-- ----- ----- ------
1 null 1 ,1
2 1 2 ,1,2
50 null 1 ,50
51 50 2 ,50,51
SQLのイメージは下記となります。木を区切る赤線をイメージしてます。
訪問経路の列挙
枝切りの使用例
create table EdaKiriSample(
ID primary key,NextID1,NextID2) as
select 'A','B','E' from dual union all
select 'B','C','D' from dual union all
select 'C','D',null from dual union all
select 'D','G','H' from dual union all
select 'E','F',null from dual union all
select 'F','B','G' from dual union all
select 'G','H',null from dual union all
select 'H','F',null from dual;
階層問い合わせでの枝切りの使用例として、下記の有向グラフでAからGに到着する経路を求めます。
同じノードへの再訪は不許可とし、AとG以外のノードは最大で3つしか訪問できないとします。
-- 訪問経路を列挙
select Level,sys_connect_by_path(ID,',') as Path
from EdaKiriSample
where ID = 'G'
start with ID = 'A'
connect by NoCycle ID in(prior NextID1,
prior NextID2)
and prior ID != 'G'
and Level <= 5
order by Level,Path;
出力結果
Level Path
----- ----------
4 ,A,B,D,G
4 ,A,E,F,G
5 ,A,B,C,D,G
Gに到着したら探索を打ち切るということで、connect by句でprior ID != 'G'を指定し、
AとG以外のノードは最大で3つしか訪問できないのでLevel <= 5を指定してます。
そして、where ID = 'G'を指定して、Gまでの経路を列挙してます。
参考リソース
"図でイメージするOracle DatabaseのSQL全集" インデックスに戻る
Copyright © 2011, Oracle Corporation Japan. All rights reserved.
無断転載を禁ず
この文書はあくまでも参考資料であり、掲載されている情報は予告なしに変更されることがあります。日本オラクル社は本書の内容に関していかなる保証もいたしません。また、本書の内容に関連したいかなる損害についても責任を負いかねます。
Oracleは米国Oracle Corporationの登録商標です。文中に参照されている各製品名及びサービス名は米国Oracle Corporationの商標または登録商標です。その他の製品名及びサービス名はそれぞれの所有者の商標または登録商標の可能性があります。
Oracle ACE の1人。
OracleSQLパズルの運営者。