3. 訪問経路の列挙（条件つき）
前問のアレンジ問題を解いてみます。
NodeT
| ID | Next1 | Next2 | Next3 |
| A | B | C | null |
| B | D | G | null |
| C | D | E | null |
| D | E | F | G |
| E | C | D | F |
| F | D | E | G |
| G | B | D | F |
下記の有向グラフで、AからDに到着する経路を求めます。同じノードへの再訪は不許可とします。また、AとD以外のノードは最大で2つしか訪問できないとし、またノードEには訪問できないとします。
有向グラフ
答えは下記となります。connect by句で、Dに到着したら探索を打ち切るということでprior ID != 'D'を指定し、AとD以外のノードは最大で2つしか訪問できないのでLevel <= 4を指定し、ノードEには訪問できないのでID != 'E'を指定しています。そして、where ID = 'D'を指定して、Dまでの経路を列挙しています。
事前に行を減らしておかない方法
select Level,sys_connect_by_path(ID,',') as path
from NodeT
where ID = 'D'
start with ID = 'A'
connect by nocycle ID in(prior Next1,
prior Next2,
prior Next3)
and prior ID != 'D'
and Level <= 4
and ID != 'E';
出力結果
| Level | path |
| 3 | ,A,B,D |
| 4 | ,A,B,G,D |
| 3 | ,A,C,D |
上記のSQLは、下記のSQLのように階層問い合わせの前に行を減らしておく方法を使って書き換えることができます。このほうが分かりやすいかもしれません。
事前にwhere句で行を減らしておく方法
select Level,sys_connect_by_path(ID,',') as path
from (select ID,Next1,Next2,Next3
from NodeT
where ID != 'E')
where ID = 'D'
start with ID = 'A'
connect by nocycle ID in(prior Next1,
prior Next2,
prior Next3)
and prior ID != 'D'
and Level <= 4;
事前に内部結合で行を減らしておく方法
select Level,sys_connect_by_path(ID,',') as path
from NodeT Join dual
on ID != 'E'
where ID = 'D'
start with ID = 'A'
connect by nocycle ID in(prior Next1,
prior Next2,
prior Next3)
and prior ID != 'D'
and Level <= 4;
最後に
今回は、枝切りの入門事項を扱いました。次回は、複雑な枝切りを扱います。
参考資料
- 『階層問合せ』
Oracleの公式マニュアルの階層問合せに関する説明です。
- 『階層問合せ疑似列』
Oracleの公式マニュアルの階層問合せに関する説明です。
- 『subquery_factoring_clause』
Oracleの公式マニュアルの再帰with句に関する説明です。
- 『再帰的副問合せのファクタリング例』
Oracleの公式マニュアルの再帰with句に関する説明です。
