Oracleの階層問い合わせ

Oracleの階層問い合わせ（6）
（枝切りの入門事項）

有向グラフで訪問経路の列挙

山岸賢治[著]

2010/02/22 14:00

ポスト

ダウンロード SourceCode (1.2 KB)

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;