9. バックトラック問題（ナップサック問題）
再帰With句で、ナップサック問題を解いてみます。最大で20kgまでの荷物を持てるとして、Valが最大になるIDの組み合わせを求めます。
create table nimotu(ID char(1) primary key,Val int,Kg int);
insert into nimotu values('A', 7,10),
('B', 2, 4),
('C', 9, 5),
('D', 4, 1),
('E', 9, 7),
('F', 7, 3),
('G', 4, 6),
('H', 5, 3);
ナップサック問題を解く
with recursive rec(ID,IDList,SumVal,SumKg) as(
select ID,cast(ID as char(20)),Val,Kg
from nimotu
union all
select b.ID,concat(a.IDList , ',' , b.ID),
a.SumVal+b.Val,a.SumKg+b.Kg
from rec a,nimotu b
where a.ID < b.ID
and a.SumKg + b.Kg <= 20)
select ID,IDList,SumVal,SumKg
from (select ID,IDList,SumVal,SumKg,
max(SumVal) over() as maxSumVal
from rec) a
where SumVal = maxSumVal;
+------+-----------+--------+-------+
| ID | IDList | SumVal | SumKg |
+------+-----------+--------+-------+
| H | C,D,E,F,H | 34 | 19 |
+------+-----------+--------+-------+
再帰With句で20kg以下となる全ての組み合わせを求めてから、Window関数のmax関数でSumValの最大値を求めています。
10. バックトラック問題（ナイト巡回問題）
再帰With句で、ナイト巡回問題を解いてみます。
create table Ban(X int,Y int); insert into Ban with tmp(Val) as( select 1 union select 2 union select 3 union select 4 union select 5) select a.Val,b.Val from tmp a Cross Join tmp b;
ナイト巡回問題を解く
with recursive rec(X,Y,LV,Path) as(
select X,Y,1,cast(concat('(' , X , '-' , Y , ')') as char(200))
from Ban
where X = 1 and Y = 1
union all
select b.X,b.Y,a.LV+1,concat(a.Path , ',' , '(' , b.X , '-' , b.Y , ')')
from rec a,Ban b
where (b.X,b.Y) in ((a.X+2,a.Y+1),
(a.X+2,a.Y-1),
(a.X-2,a.Y+1),
(a.X-2,a.Y-1),
(a.X+1,a.Y+2),
(a.X+1,a.Y-2),
(a.X-1,a.Y+2),
(a.X-1,a.Y-2))
and Find_IN_Set(concat('(' , b.X , '-' , b.Y , ')') , a.Path) = false)
select Path
from rec
where LV = 5 * 5;
+---------------------------------------------------------------+
| Path |
+---------------------------------------------------------------+
| (1-1),(2-3),(1-5),(3-4),(5-5),(4-3),(5-1),(3-2),(5-3),(4-1), |
| (2-2),(1-4),(3-5),(5-4),(4-2),(2-1),(1-3),(2-5),(4-4),(5-2), |
| (3-3),(4-5),(2-4),(1-2),(3-1) |
解は304通りあるので、1個目の解を、適宜改行して表示しています。
経路を記憶しつつ、Find_IN_Set関数で訪問済みでないことをチェックしています。
11. OracleのSearch句（深さ優先探索）を模倣
OracleのSearch句（深さ優先探索）を模倣してみます。以下のサンプルデータを見てください。
create table DepthFirstT(ID int primary key,OyaID int); insert into DepthFirstT values( 1,null); insert into DepthFirstT values( 2, 1); insert into DepthFirstT values( 3, 1); insert into DepthFirstT values( 4, 1); insert into DepthFirstT values( 5, 3); insert into DepthFirstT values( 6, 3); insert into DepthFirstT values( 7, 4); insert into DepthFirstT values( 8, 4); insert into DepthFirstT values( 9, 6); insert into DepthFirstT values(10, 7); insert into DepthFirstT values(20,null); insert into DepthFirstT values(21, 20); insert into DepthFirstT values(22, 20); insert into DepthFirstT values(23, 21); insert into DepthFirstT values(24, 21);
Oracleの再帰With句では、Search句を使って、深さ優先探索順にソートできます。MySQL 8.0で、下記のOracleのSQLと同じ結果を取得してみます。
模倣対象のOracleのSQL
with rec(TreeID,ID,OyaID,LV,Path) as(
select ID,ID,OyaID,1,to_char(ID)
from DepthFirstT
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,DepthFirstT b
where a.ID = b.OyaID)
search depth first by ID desc set SortKey
select TreeID,ID,OyaID,LV,Path from rec
order by SortKey;
TreeID ID OyaID LV Path
------ -- ----- -- --------
20 20 null 1 20
20 22 20 2 20,22
20 21 20 2 20,21
20 24 21 3 20,21,24
20 23 21 3 20,21,23
1 1 null 1 1
1 4 1 2 1,4
1 8 4 3 1,4,8
1 7 4 3 1,4,7
1 10 7 4 1,4,7,10
1 3 1 2 1,3
1 6 3 3 1,3,6
1 9 6 4 1,3,6,9
1 5 3 3 1,3,5
1 2 1 2 1,2
Search句（深さ優先探索）を模倣
with recursive tmp as(
select ID,OyaID,
LPad(Row_Number() over(order by ID desc),3,'0') as rn
from DepthFirstT),
rec(TreeID,ID,OyaID,LV,Path,SortStr) as(
select ID,ID,OyaID,1,
cast(ID as char(200)),
cast(rn as char(200))
from tmp
where OyaID is null
union all
select a.TreeID,b.ID,b.OyaID,a.LV+1,
concat(a.Path , ',' , b.ID),
concat(a.SortStr , ',' , b.rn)
from rec a Join tmp b
on a.ID = b.OyaID)
select * from rec order by SortStr;
+--------+------+-------+------+----------+-----------------+
| TreeID | ID | OyaID | LV | Path | SortStr |
+--------+------+-------+------+----------+-----------------+
| 20 | 20 | NULL | 1 | 20 | 005 |
| 20 | 22 | 20 | 2 | 20,22 | 005,003 |
| 20 | 21 | 20 | 2 | 20,21 | 005,004 |
| 20 | 24 | 21 | 3 | 20,21,24 | 005,004,001 |
| 20 | 23 | 21 | 3 | 20,21,23 | 005,004,002 |
| 1 | 1 | NULL | 1 | 1 | 015 |
| 1 | 4 | 1 | 2 | 1,4 | 015,012 |
| 1 | 8 | 4 | 3 | 1,4,8 | 015,012,008 |
| 1 | 7 | 4 | 3 | 1,4,7 | 015,012,009 |
| 1 | 10 | 7 | 4 | 1,4,7,10 | 015,012,009,006 |
| 1 | 3 | 1 | 2 | 1,3 | 015,013 |
| 1 | 6 | 3 | 3 | 1,3,6 | 015,013,010 |
| 1 | 9 | 6 | 4 | 1,3,6,9 | 015,013,010,007 |
| 1 | 5 | 3 | 3 | 1,3,5 | 015,013,011 |
| 1 | 2 | 1 | 2 | 1,2 | 015,014 |
+--------+------+-------+------+----------+-----------------+
search depth first by ID desc set SortKeyを模倣するので、最初に、Row_Number関数でIDの降順でのサロゲートキーを作り、LPad関数で前ゼロを付け、列別名rnとしています。
次に、根からの経路上のrnをSortStrという列に追加していき、最後に、order by SortStrとしています。
12. OracleのSearch句（幅優先探索）を模倣
OracleのSearch句（幅優先探索）を模倣します。以下のサンプルデータを見てください。
create table BreadthFirstT(ID int primary key,OyaID int); insert into BreadthFirstT values( 1,null); insert into BreadthFirstT values( 2, 1); insert into BreadthFirstT values( 3, 1); insert into BreadthFirstT values( 8, 2); insert into BreadthFirstT values( 9, 2); insert into BreadthFirstT values( 5, 3); insert into BreadthFirstT values( 6, 3); insert into BreadthFirstT values(30,null); insert into BreadthFirstT values(31, 30);
Oracleの再帰With句では、Search句を使って、幅優先探索順にソートできます。MySQL 8.0で、下記のOracleのSQLと同じ結果を取得してみます。
模倣対象のOracleのSQL
with rec(ID,OyaID,LV,Path) as( select ID,OyaID,1,to_char(ID) from BreadthFirstT where OyaID is null union all select b.ID,b.OyaID,a.LV+1,a.Path || ',' || to_char(b.ID) from rec a,BreadthFirstT b where a.ID = b.OyaID) search breadth first by ID set SortKey select ID,OyaID,LV,Path from rec order by SortKey; ID OyaID LV Path -- ----- -- ----- 1 null 1 1 30 null 1 30 2 1 2 1,2 3 1 2 1,3 31 30 2 30,31 5 3 3 1,3,5 6 3 3 1,3,6 8 2 3 1,2,8 9 2 3 1,2,9
Search句（幅優先探索）を模倣
with recursive rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,cast(ID as char(200))
from BreadthFirstT
where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,concat(a.Path , ',' , b.ID)
from rec a Join BreadthFirstT b
on a.ID = b.OyaID)
select * from rec order by LV,ID;
search breadth first by ID set SortKeyでの幅優先探索を模倣するので、ノードのレベルを第1ソートキーとし、IDの値を第2ソートキーにしています。
13. OracleのCycle句を模倣
OracleのCycle句を模倣します。以下のサンプルデータを見てください。
create table CycleT(ID int primary key,NextID int); insert into CycleT values(1,2); insert into CycleT values(2,3); insert into CycleT values(3,4); insert into CycleT values(4,1); insert into CycleT values(5,5); insert into CycleT values(7,8); insert into CycleT values(8,7);
Oracleの再帰With句では、Cycle句を使って、閉路を検知することができます。MySQL 8.0で、下記のOracleのSQLと同じ結果を取得してみます。
模倣対象のOracleのSQL
with rec(ID,NextID,Path) as( select ID,NextID,to_char(ID) from CycleT where ID in(1,5,7) union all select b.ID,b.NextID,a.Path || ',' || to_char(b.ID) from rec a,CycleT b where a.NextID = b.ID) CYCLE ID SET IsLoop TO 'Y' DEFAULT 'N' select ID,NextID,Path,IsLoop from rec order by Path; ID NextID Path IsLoop -- ------ --------- ------ 1 2 1 N 2 3 1,2 N 3 4 1,2,3 N 4 1 1,2,3,4 N 1 2 1,2,3,4,1 Y 5 5 5 N 5 5 5,5 Y 7 8 7 N 8 7 7,8 N 7 8 7,8,7 Y
Cycle句を模倣
with recursive rec(ID,NextID,Path,IsLoop) as(
select ID,NextID,cast(ID as char(20)),false
from CycleT
where ID in(1,5,7)
union all
select b.ID,b.NextID,concat(a.Path , ',' , b.ID),
Find_IN_Set(b.ID,a.Path)
from rec a Join CycleT b
on a.NextID = b.ID
where a.IsLoop = false)
select ID,NextID,Path,
If(IsLoop,'Y','N') as IsLoop
from rec order by Path;
ループの検知のために、経路を記憶しつつ、Find_IN_Set関数で、訪問済みかをチェックしています。
最後に
今回は、再帰With句を扱いました。次回は、『SQLパズル 第2版』の問題をMySQL 8.0で解きます。
