4. データ探索（木構造）
再帰With句で木構造なデータの探索を行うことができます。
create table TreeTable(ID int primary key,OyaID int);
insert into TreeTable values( 1,null),
( 2, 1),
( 3, 1),
( 4, 2),
( 5, 3),
(10,null),
(11, 10),
(12, 10);
木の根となる条件を、OyaID is null、親子条件を、親のID = 子のOyaID として木構造なデータを探索します。根からの経路や、各ノードのレベルも求めます。
with recursive rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,cast(ID as char(10))
from TreeTable
where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
concat(a.Path , ',' , b.ID)
from rec a Join TreeTable b
on a.ID = b.OyaID)
select * from rec;
+------+-------+------+-------+
| ID | OyaID | LV | Path |
+------+-------+------+-------+
| 1 | NULL | 1 | 1 |
| 10 | NULL | 1 | 10 |
| 2 | 1 | 2 | 1,2 |
| 3 | 1 | 2 | 1,3 |
| 11 | 10 | 2 | 10,11 |
| 12 | 10 | 2 | 10,12 |
| 4 | 2 | 3 | 1,2,4 |
| 5 | 3 | 3 | 1,3,5 |
+------+-------+------+-------+
非再帰項で、OyaIDがnullの行を木の根として出力して、再帰項で、親子条件である、親のID = 子のOyaIDを満たす行を再帰的に出力しています。
非再帰項の段階での、SQLのイメージは下記となります。非再帰項による木の根の作成をイメージしています。
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
5. データ探索（有向グラフ）
再帰With句で有向グラフの探索を行うことができます。
create table GraphTable(ID int primary key,NextID int);
insert into GraphTable values(1,2),
(2,3),
(3,4),
(4,1),
(7,8),
(8,7);
ID = 1のノードから到達可能なノードと、その経路を列挙してみます。
with recursive rec(ID,NextID,Path) as(
select ID,NextID,cast(ID as char(10))
from GraphTable
where ID = 1
union all
select b.ID,b.NextID,concat(a.Path , ',' , b.ID)
from rec a Join GraphTable b
on a.NextID = b.ID
where Find_IN_Set(b.ID,a.Path) = false)
select * from rec;
+------+--------+---------+
| ID | NextID | Path |
+------+--------+---------+
| 1 | 2 | 1 |
| 2 | 3 | 1,2 |
| 3 | 4 | 1,2,3 |
| 4 | 1 | 1,2,3,4 |
+------+--------+---------+
この有向グラフには、閉路（Cycle）が存在するので、経路を記憶しつつ、Find_IN_Set関数で訪問済みでないことをチェックしています。
非再帰項の段階での、SQLのイメージは下記となります。非再帰項による木の根の作成をイメージしています。
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージし、訪問済みノードへの再訪防止を赤バツでイメージしています。
6. 枝切り（レベル制限）
再帰With句の探索の枝切りについて解説します。
create table LevelEdaKiri(ID int primary key,OyaID int);
insert into LevelEdaKiri values(10,null),
(11, 10),
(12, 11),
(13, 12),
(14, 13),
(31, 10),
(32, 31),
(33, 32);
ID = 10 の行から探索を始めて、到達可能なノードを表示します。ただし、ノードのレベルを3以下に制限します。
with recursive rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,cast(ID as char(20))
from LevelEdaKiri
where ID = 10
union all
select b.ID,b.OyaID,a.LV+1,
concat(a.Path , ',' , b.ID)
from rec a Join LevelEdaKiri b
on a.ID = b.OyaID
where a.LV+1 <= 3)
select * from rec;
+------+-------+------+----------+
| ID | OyaID | LV | Path |
+------+-------+------+----------+
| 10 | NULL | 1 | 10 |
| 11 | 10 | 2 | 10,11 |
| 31 | 10 | 2 | 10,31 |
| 12 | 11 | 3 | 10,11,12 |
| 32 | 31 | 3 | 10,31,32 |
+------+-------+------+----------+
上記のSQLのように、再帰項のwhere句で条件指定して枝切りを行うことができます。
非再帰項の段階での、SQLのイメージは下記となります。非再帰項による木の根の作成をイメージしています。
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
7. 枝切り（外部結合後のwhere句）
再帰項での、外部結合後のwhere句で枝切りを行うこともできます。子ノードがなくても行を出力したい時に使います。
create table OuterJoinEdakiri(ID int primary key,OyaID int);
insert into OuterJoinEdakiri values( 1,null),
( 2, 1),
( 3, 2),
( 4, 3),
( 5, 3),
( 6, 2),
(30,null),
(31, 30),
(32, 30),
(33, 31),
(34, 33),
(60,null);
OyaID is nullの行から探索を始めて、到達可能なノードを表示します。ただし、ノードのレベルを3以下に制限し、レベル1で到達可能なノード、レベル2で到達可能なノード（なければnull）、レベル3で到達可能なノード（なければnull）をそれぞれ表示します。
with recursive rec(TreeID,ID,OyaID,LV,Path) as(
select ID,ID,OyaID,1,cast(ID as char(20))
from OuterJoinEdakiri
where OyaID is null
union all
select a.TreeID,b.ID,b.OyaID,a.LV+1,
concat(a.Path , ',' , IfNull(b.ID,'null'))
from rec a Left Join OuterJoinEdakiri b
on a.ID = b.OyaID
where a.LV+1 <= 3)
select * from rec order by Path;
+--------+------+-------+------+--------------+
| TreeID | ID | OyaID | LV | Path |
+--------+------+-------+------+--------------+
| 1 | 1 | NULL | 1 | 1 |
| 1 | 2 | 1 | 2 | 1,2 |
| 1 | 3 | 2 | 3 | 1,2,3 |
| 1 | 6 | 2 | 3 | 1,2,6 |
| 30 | 30 | NULL | 1 | 30 |
| 30 | 31 | 30 | 2 | 30,31 |
| 30 | 33 | 31 | 3 | 30,31,33 |
| 30 | 32 | 30 | 2 | 30,32 |
| 30 | NULL | NULL | 3 | 30,32,null |
| 60 | 60 | NULL | 1 | 60 |
| 60 | NULL | NULL | 2 | 60,null |
| 60 | NULL | NULL | 3 | 60,null,null |
+--------+------+-------+------+--------------+
非再帰項の段階での、SQLのイメージは下記となります。非再帰項による木の根の作成をイメージしています。
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
8. 枝切り（union集合演算）
union集合演算の重複排除機能で枝切りを行うことができます。
create table UnionEdakiri(ID int primary key,Next1 int,Next2 int);
insert into UnionEdakiri values(10, 11, 13),
(11, 12, 14),
(12, 13,null),
(13, 11, 12),
(14, 10, 13),
(20, 21, 22);
ID = 10のノードから探索を開始して、訪問可能なノードを列挙してみます。レベルや経路などは表示しません。
with recursive rec(ID,Next1,Next2) as(
select ID,Next1,Next2
from UnionEdakiri
where ID = 10
union
select b.ID,b.Next1,b.Next2
from rec a Join UnionEdakiri b
on b.ID in (a.Next1,a.Next2))
select * from rec;
+------+-------+-------+
| ID | Next1 | Next2 |
+------+-------+-------+
| 10 | 11 | 13 |
| 11 | 12 | 14 |
| 13 | 11 | 12 |
| 12 | 13 | NULL |
| 14 | 10 | 13 |
+------+-------+-------+
再帰With句のselect句の列リストによっては、union集合演算で枝切りを行うと、ループの検知などが不要になりシンプルなSQLとなります。
