トップページに戻る
次のSQLパズルへ
前のSQLパズルへ
10-287 木の高さ制限による枝切り
SQLパズル
RootListT
FromP ToP
----- ---
01 02
01 03
01 04
01 05
01 06
01 07
01 08
01 09
02 01
02 03
02 04
02 05
02 06
02 08
02 09
03 01
03 02
03 04
03 05
03 06
03 07
03 08
03 09
04 01
04 02
04 03
04 05
04 06
04 07
04 08
04 09
04 0G
05 01
05 02
05 03
05 04
05 07
05 09
05 0A
05 0B
05 0C
05 0D
05 0E
05 0F
06 01
06 02
06 03
06 04
06 0A
06 0B
06 0C
06 0D
06 0E
06 0F
07 01
07 03
07 04
07 05
07 09
07 0A
07 0B
07 0D
07 0E
07 0F
08 01
08 02
08 03
08 04
08 0A
08 0B
08 0C
08 0D
08 0E
08 0F
09 01
09 02
09 03
09 04
09 05
09 07
09 0A
09 0B
09 0C
09 0D
09 0E
09 0F
0A 05
0A 06
0A 07
0A 08
0A 09
0A 0B
0A 0C
0A 0D
0A 0E
0A 0F
0B 05
0B 06
0B 07
0B 08
0B 09
0B 0A
0B 0C
0B 0D
0B 0F
0C 05
0C 06
0C 08
0C 09
0C 0A
0C 0B
0C 0D
0C 0E
0C 0F
0D 05
0D 06
0D 07
0D 08
0D 09
0D 0A
0D 0B
0D 0C
0D 0E
0D 0F
0E 05
0E 06
0E 07
0E 08
0E 09
0E 0A
0E 0C
0E 0D
0E 0F
0F 05
0F 06
0F 07
0F 08
0F 09
0F 0A
0F 0B
0F 0C
0F 0D
0F 0F
0G 04
0G 0F
0G 0H
0H 0G
0H 01
FromPが01からスタートして、
ToPが07の行に到着するまでの経路を、
中間地点の数の降順で列挙する。
ただし、中間地点の数は、2個までとする。
出力結果
PathList
-----------
01,02,01,07
01,02,03,07
01,02,04,07
01,02,05,07
01,02,09,07
01,03,01,07
01,03,04,07
01,03,05,07
01,03,09,07
01,04,01,07
01,04,03,07
01,04,05,07
01,04,09,07
01,05,01,07
01,05,03,07
01,05,04,07
01,05,09,07
01,05,0A,07
01,05,0B,07
01,05,0D,07
01,05,0E,07
01,05,0F,07
01,06,01,07
01,06,03,07
01,06,04,07
01,06,0A,07
01,06,0B,07
01,06,0D,07
01,06,0E,07
01,06,0F,07
01,08,01,07
01,08,03,07
01,08,04,07
01,08,0A,07
01,08,0B,07
01,08,0D,07
01,08,0E,07
01,08,0F,07
01,09,01,07
01,09,03,07
01,09,04,07
01,09,05,07
01,09,0A,07
01,09,0B,07
01,09,0D,07
01,09,0E,07
01,09,0F,07
01,03,07
01,04,07
01,05,07
01,09,07
01,07
データ作成スクリプト
create table RootListT(FromP,ToP) as
select '01','02' from dual union select '01','03' from dual union select '01','04' from dual union
select '01','05' from dual union select '01','06' from dual union select '01','07' from dual union
select '01','08' from dual union select '01','09' from dual union select '02','01' from dual union
select '02','03' from dual union select '02','04' from dual union select '02','05' from dual union
select '02','06' from dual union select '02','08' from dual union select '02','09' from dual union
select '03','01' from dual union select '03','02' from dual union select '03','04' from dual union
select '03','05' from dual union select '03','06' from dual union select '03','07' from dual union
select '03','08' from dual union select '03','09' from dual union select '04','01' from dual union
select '04','02' from dual union select '04','03' from dual union select '04','05' from dual union
select '04','06' from dual union select '04','07' from dual union select '04','08' from dual union
select '04','09' from dual union select '04','0G' from dual union select '05','01' from dual union
select '05','02' from dual union select '05','03' from dual union select '05','04' from dual union
select '05','07' from dual union select '05','09' from dual union select '05','0A' from dual union
select '05','0B' from dual union select '05','0C' from dual union select '05','0D' from dual union
select '05','0E' from dual union select '05','0F' from dual union select '06','01' from dual union
select '06','02' from dual union select '06','03' from dual union select '06','04' from dual union
select '06','0A' from dual union select '06','0B' from dual union select '06','0C' from dual union
select '06','0D' from dual union select '06','0E' from dual union select '06','0F' from dual union
select '07','01' from dual union select '07','03' from dual union select '07','04' from dual union
select '07','05' from dual union select '07','09' from dual union select '07','0A' from dual union
select '07','0B' from dual union select '07','0D' from dual union select '07','0E' from dual union
select '07','0F' from dual union select '08','01' from dual union select '08','02' from dual union
select '08','03' from dual union select '08','04' from dual union select '08','0A' from dual union
select '08','0B' from dual union select '08','0C' from dual union select '08','0D' from dual union
select '08','0E' from dual union select '08','0F' from dual union select '09','01' from dual union
select '09','02' from dual union select '09','03' from dual union select '09','04' from dual union
select '09','05' from dual union select '09','07' from dual union select '09','0A' from dual union
select '09','0B' from dual union select '09','0C' from dual union select '09','0D' from dual union
select '09','0E' from dual union select '09','0F' from dual union select '0A','05' from dual union
select '0A','06' from dual union select '0A','07' from dual union select '0A','08' from dual union
select '0A','09' from dual union select '0A','0B' from dual union select '0A','0C' from dual union
select '0A','0D' from dual union select '0A','0E' from dual union select '0A','0F' from dual union
select '0B','05' from dual union select '0B','06' from dual union select '0B','07' from dual union
select '0B','08' from dual union select '0B','09' from dual union select '0B','0A' from dual union
select '0B','0C' from dual union select '0B','0D' from dual union select '0B','0F' from dual union
select '0C','05' from dual union select '0C','06' from dual union select '0C','08' from dual union
select '0C','09' from dual union select '0C','0A' from dual union select '0C','0B' from dual union
select '0C','0D' from dual union select '0C','0E' from dual union select '0C','0F' from dual union
select '0D','05' from dual union select '0D','06' from dual union select '0D','07' from dual union
select '0D','08' from dual union select '0D','09' from dual union select '0D','0A' from dual union
select '0D','0B' from dual union select '0D','0C' from dual union select '0D','0E' from dual union
select '0D','0F' from dual union select '0E','05' from dual union select '0E','06' from dual union
select '0E','07' from dual union select '0E','08' from dual union select '0E','09' from dual union
select '0E','0A' from dual union select '0E','0C' from dual union select '0E','0D' from dual union
select '0E','0F' from dual union select '0F','05' from dual union select '0F','06' from dual union
select '0F','07' from dual union select '0F','08' from dual union select '0F','09' from dual union
select '0F','0A' from dual union select '0F','0B' from dual union select '0F','0C' from dual union
select '0F','0D' from dual union select '0F','0F' from dual union select '0G','04' from dual union
select '0G','0F' from dual union select '0G','0H' from dual union select '0H','0G' from dual union
select '0H','01' from dual;
SQL
col PathList for a20
select substr(sys_connect_by_path(FromP,','),2) || ',' || ToP as PathList
from RootListT
where connect_by_isleaf = 1
and ToP = '07'
start with FromP = '01'
connect by nocycle prior ToP = FromP
and prior ToP != '07'
and Level <= 3
order by Level desc,PathList;
解説
階層問い合わせでは、connect by句に
ノード間の親子条件以外に、
枝切りの条件を記述できます。
木の高さを条件とした枝切りや、
探索の打ち切り条件を指定した枝切りが可能です。
テレションショッピングの高枝切りバサミのイメージです ;-)
10-139 最短距離問題
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
階層問い合わせの結果の行数を見積もる時には、下記のように、
木の高さを条件とした枝切りを行い、
count関数とdecode関数を使うと便利です。
select
count(decode(Level,1,1)) as L1,
count(decode(Level,2,1)) as L2,
count(decode(Level,3,1)) as L3,
count(decode(Level,4,1)) as L4,
count(decode(Level,5,1)) as L5,
count(decode(Level,6,1)) as L6,
count(decode(Level,7,1)) as L7,
count(decode(Level,8,1)) as L8
from RootListT
where connect_by_isleaf = 1
and ToP = '07'
start with FromP = '01'
connect by nocycle prior ToP = FromP
and prior ToP != '07'
and Level <= 8;
L1 L2 L3 L4 L5 L6 L7 L8
-- -- -- --- ---- ----- ----- ------
1 4 47 327 2434 15627 92095 479158
木の高さを制限しないと、組合せ爆発が発生した場合に、SQLが終わらなくなります・・・
組合せ爆発 - Wikipedia
最長片道きっぷ - [3-6] 全探索で（泥沼編）
アルゴリズム講座/応用編/枝刈り
PL/SQL5 階層問い合わせを模倣(nocycle対応)
10-300 紐づく子供がいたら、自分と子孫を、子供の値で埋める