PostgreSQL,OracleのWITH(WITH RECURSIVE)句で循環検出に使えるCYCLE句
検索して見つかる公式ドキュメント以外の日本語資料がなく、チャットAIもあまり良い回答をしてくれなかったので……
要約
CYCLE 句を使うと、自分で循環検出用の列などを定義する必要なく循環検出を含む SQL が書ける
循環検出用の列は自動で追加してくれる
公式 (公認) の日本語説明を読む
このように閉路のあるデータ構造の時には、cycle句を使うと、親子関係があるけど経路上で訪問済であるノードへの再訪問を考慮した探索を行うことができます。
code:sql
-- 再帰with句で閉路のある探索2 (引用時にフォーマットした)
WITH rec(ID, NextID, LV, Path) AS (
SELECT ID, NextID, 1, TO_CHAR(ID)
FROM GraphData
WHERE ID = 50
UNION ALL
SELECT b.ID, b.NextID, a.LV + 1,
a.Path || ',' || TO_CHAR(b.ID)
FROM rec a, GraphData b
WHERE a.NextID = b.ID
)
CYCLE ID SET IsLoop TO 'Y' DEFAULT 'N'
SELECT * FROM rec;
出力結果
code:txt
ID NextID LV Path IsLoop
-- ------ -- ----------- ------
50 51 1 50 N
51 52 2 50,51 N
52 50 3 50,51,52 N
50 51 4 50,51,52,50 Y
cycle ID set IsLoop to 'Y' default 'N' によって、子ノードとID列が一致する訪問済ノードが存在しなければ、子ノードのIsLoop列にNをセットし、そのノードからの探索を継続します。
子ノードとID列が一致する訪問済ノードが存在したら、cycleが存在すると判定して、子ノードのIsLoop列にYをセットし、そのノードからの探索を打ち切ります。
(リンク先で図の確認を推奨)
サイクル検出を簡略化する組み込み構文があります。 上記のクエリ (リンク先参照) は、次のように記述することもできます。
code:sql
WITH RECURSIVE search_graph(id, link, data, depth) AS (
SELECT g.id, g.link, g.data, 1
FROM graph g
UNION ALL
SELECT g.id, g.link, g.data, sg.depth + 1
FROM graph g, search_graph sg
WHERE g.id = sg.link
) CYCLE id SET is_cycle USING path
SELECT * FROM search_graph;
また、内部的に上記の形式 (リンク先参照) に書き換えられます。
CYCLE句は、最初にサイクル検出のために追跡する列のリストを指定し、次にサイクルが検出されたかどうかを示す列名、最後にパスを追跡する別の列の名前を指定します。
サイクル列とパス列は、CTEの出力行に暗黙的に追加されます。
一番シンプルなテーブルで試してみる
PostgreSQL にて、以下のテーブルで子の id から全ての親を辿る。
code:schema.sql
CREATE TABLE tree (
id integer PRIMARY KEY,
parent_id integer
);
INSERT INTO tree VALUES
(0, null),
(1, 3), -- ここで循環
(2, 1),
(3, 2),
(4, 3);
無限ループする SQL
code:sql
WITH RECURSIVE parent_tree (id, parent_id) AS (
-- 初期クエリ
SELECT id, parent_id
FROM tree
WHERE id = 4 -- ID指定
UNION ALL
-- 再帰的なクエリ
SELECT t.id, t.parent_id
FROM tree t
JOIN parent_tree pt ON t.id = pt.parent_id
)
SELECT *
FROM parent_tree
LIMIT 10; -- 安全のため適当なところで止める (PostrgreSQL 専用)
結果
code:result.txt
id | parent_id
----+-----------
4 | 3
3 | 2
2 | 1
1 | 3
3 | 2
2 | 1
1 | 3
3 | 2
2 | 1
1 | 3
(10 rows)
4321321321... とループしている
CYCLE 句を使ってみる
code:sql
WITH RECURSIVE parent_tree (id, parent_id) AS (
-- 初期クエリ
SELECT id, parent_id
FROM tree
WHERE id = 4 -- ID指定
UNION ALL
-- 再帰的なクエリ
SELECT t.id, t.parent_id
FROM tree t
JOIN parent_tree pt ON t.id = pt.parent_id
) CYCLE id SET is_cycle USING path -- 変更点はこの行のみ
SELECT *
FROM parent_tree
LIMIT 10; -- 不要だけど一応
結果
code:result.txt
id | parent_id | is_cycle | path
----+-----------+----------+-----------------------
4 | 3 | f | {(4)}
3 | 2 | f | {(4),(3)}
2 | 1 | f | {(4),(3),(2)}
1 | 3 | f | {(4),(3),(2),(1)}
3 | 2 | t | {(4),(3),(2),(1),(3)}
(5 rows)
重複が見つかったら is_cycle が true になり、それ以上の探索を打ち切っている (Oracle の説明通り)
is_cycle 列と path 列は自動で追加されている (PostgreSQL の説明通り)
1行追加するだけで対応できる。とてもよい
Oracle の説明だと USING path が省略されていたけど、 PostgreSQL では必須っぽい