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のイメージは下記となります。非再帰項による木の根の作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image03-01.png)
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image03-02.png)
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のイメージは下記となります。非再帰項による木の根の作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image04-01.png)
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージし、訪問済みノードへの再訪防止を赤バツでイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image04-02.png)
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のイメージは下記となります。非再帰項による木の根の作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image05-01.png)
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image05-02.png)
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のイメージは下記となります。非再帰項による木の根の作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image06-01.png)
再帰項の段階での、SQLのイメージは下記となります。再帰項による木のノードの作成をイメージしています。
![](http://cz-cdn.shoeisha.jp/static/images/article/2679/image06-02.png)
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となります。