一覧DB-10-2 · 発展SQLと別のデータモデル

再帰CTEと循環の検出

六項目の階層で子孫と祖先を取得し、深さの上限を変えます。その後に循環する参照を作り、UNIONによる重複除去と、経路を持って循環を検出する方法を比較します。最後に参照を戻して階層を確認します。

説明

親IDを持つ表から子孫をすべて取得するには、深さが決まった自己結合だけでは足りません。再帰CTEは開始行を選び、その結果から次の行を繰り返し求めるSQLです。開始点、進む方向、停止条件を明示します。

六項目の階層で子孫と祖先を取得し、深さの上限を変えます。その後に循環する参照を作り、UNIONによる重複除去と、経路を持って循環を検出する方法を比較します。最後に参照を戻して階層を確認します。

1親IDを持つ六項目

教材の下に通信とDB、その下にTCP・UDP・SQLを置きます。

CREATE TABLE nodes(id INTEGER PRIMARY KEY,name TEXT,parent_id INTEGER REFERENCES nodes(id)親のIDを参照) STRICT; INSERT INTO nodes VALUES(1,'教材',NULL),(2,'通信',1),(3,'DB',1),(4,'TCP',2),(5,'UDP',2),(6,'SQL',3); SELECT * FROM nodes全項目と親を表示 ORDER BY id;

parent_idは一つ上の項目を参照します。外部キーは親の存在を検査しますが、循環のない木であることまでは保証しません。最初は1が根で、各項目へ根から一つの経路があります。

2開始行から子を繰り返し取得する

ID 1を深さ0として再帰を始めます。

WITH RECURSIVE walk再帰的な検索結果(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=1開始点 UNION ALL SELECT n.id,n.name,w.depth+1一段下へ進む FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id現在行を親とする子) SELECT * FROM walk ORDER BY depth,id;

深さ0に教材、1に通信とDB、2にTCP・UDP・SQLです。最初のSELECTが開始部分、UNION ALLの後が再帰部分です。再帰部分は直前に得た行のidを親に持つ行を追加し、追加する行がなくなると終了します。

3深さを一段までに制限する

再帰側にdepth<1を加えます。

WITH RECURSIVE walk(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=1 UNION ALL SELECT n.id,n.name,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.depth<1次へ進んでよい現在の深さ) SELECT * FROM walk ORDER BY depth,id;

教材・通信・DBの三行です。現在の深さが0のときだけ次を追加するため、結果の最大深さは1です。上限を現在行へ掛けるのか、追加後の深さへ掛けるのかを確認します。

4開始点を通信へ変える

ID 2を根として取得します。

WITH RECURSIVE walk(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=2今回の開始点を通信にする UNION ALL SELECT n.id,n.name,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id) SELECT * FROM walk ORDER BY depth,id;

通信が深さ0、TCPとUDPが深さ1になります。depthは表に固定保存された絶対的な深さではなく、この検索の開始点から数えた値です。DBとSQLは通信の子孫ではないため含まれません。

5TCPから親へ向きを逆にたどる

ID 4からparent_idへ進みます。

WITH RECURSIVE ancestors(id,name,parent_id,depth) AS (SELECT id,name,parent_id,0 FROM nodes WHERE id=4TCPを開始点にする UNION ALL SELECT n.id,n.name,n.parent_id,a.depth+1 FROM nodes AS n JOIN ancestors AS a ON n.id=a.parent_id現在行の親IDへ進む) SELECT id,name,depth FROM ancestors ORDER BY depth;

TCP→通信→教材です。子を探すときはn.parent_id=現在id、親を探すときはn.id=現在parent_idでした。結合条件の向きが、探索する関係を決めます。

6外部キーを満たした循環を作る

根だった教材の親をTCPにします。

UPDATE nodes SET parent_id=4 WHERE id=1根を子孫へ結び循環させる; SELECT id,parent_id FROM nodes WHERE id IN (1,2,4) ORDER BY id;

1の親が4、4の親が2、2の親が1となり循環します。参照先の行はすべて存在するため、外部キー違反にはなりません。このまま停止条件なしのUNION ALLでたどると、同じ項目を繰り返します。

7IDだけをUNIONで重複除去する

結果列をIDだけにし、UNIONで既出のIDを取り除きます。

WITH RECURSIVE reach(id)既出判定の対象はIDだけ AS (SELECT 1 UNION SELECT同じ結果行を再追加しない n.id FROM nodes AS n JOIN reach AS r ON n.parent_id=r.id) SELECT id FROM reach ORDER BY id;

1～6を一回ずつ取得して終了します。UNIONは結果行全体の重複を除きます。ここに増え続けるdepthを追加すると、同じIDでも別の行になり、同じ停止方法にはなりません。また、この結果だけではどこに循環があったかは分かりません。

8経路にあるIDを再訪したら循環として止める

/1/のように区切った経路を持ち、再訪行にcycle=1を付けます。

WITH RECURSIVE walk(id,path,cycle) AS (SELECT 1,'/1/',0 UNION ALL SELECT n.id,w.path||n.id||'/'経路へ次のIDを追加,instr(w.path,'/'||n.id||'/')>0同じIDが経路にあるか FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.cycle=0循環を検出した行からは進まない) SELECT id,path,cycle FROM walk ORDER BY path;

経路/1/2/4/1/にcycle=1が付き、その行から先へは進みません。IDを/で囲むのは、1を11の一部と取り違えないためです。経路ごとの再訪を検出するので、どのつながりが循環を作ったかも表示できます。

9循環のある行だけを取得する

同じ再帰結果からcycle=1に絞ります。

WITH RECURSIVE walk(id,path,cycle) AS (SELECT 1,'/1/',0 UNION ALL SELECT n.id,w.path||n.id||'/',instr(w.path,'/'||n.id||'/')>0 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.cycle=0) SELECT id,path FROM walk WHERE cycle=1循環が見つかった経路だけ表示;

ID 1と経路/1/2/4/1/の一行です。深さ上限は処理量を制限しますが、それだけでは循環がないことを証明しません。訪問経路と繰返しの判定を別に持つと、上限超過と循環を区別できます。

10親参照を戻して全体を確認する

ID 1の親をNULLへ戻します。

UPDATE nodes SET parent_id=NULL根を元へ戻す WHERE id=1; WITH RECURSIVE walk(id,depth) AS (SELECT id,0 FROM nodes WHERE parent_id IS NULL根の行から開始 UNION ALL SELECT n.id,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id) SELECT COUNT(*) AS nodes,MAX(depth)到達した最大深さ AS max_depth FROM walk;

六項目、最大深さ2です。今回のデータでは全項目が根からたどれます。開始点と停止条件に加え、参照の整合性と到達できる範囲も確認して、階層の取得を組み立てます。

まとめ

再帰CTEは開始部分と再帰部分を分け、どちらへ進むかと停止条件を明示します。

外部キーが有効でも、親子関係に循環がないことは別の条件です。

UNIONの行全体の重複除去と、経路ごとの循環検出では、残る情報が異なります。

操作履歴と解説を振り返れます。

SQLite 3.54.0

1
CREATE TABLE nodes(id INTEGER PRIMARY KEY,name TEXT,parent_id INTEGER REFERENCES nodes(id)) STRICT; INSERT INTO nodes VALUES(1,'教材',NULL),(2,'通信',1),(3,'DB',1),(4,'TCP',2),(5,'UDP',2),(6,'SQL',3); SELECT * FROM nodes ORDER BY id;
╭────┬──────┬───────────╮
│ id │ name │ parent_id │
╞════╪══════╪═══════════╡
│  1 │ 教材 │ NULL      │
│  2 │ 通信 │         1 │
│  3 │ DB   │         1 │
│  4 │ TCP  │         2 │
│  5 │ UDP  │         2 │
│  6 │ SQL  │         3 │
╰────┴──────┴───────────╯
2
WITH RECURSIVE walk(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=1 UNION ALL SELECT n.id,n.name,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id) SELECT * FROM walk ORDER BY depth,id;
╭────┬──────┬───────╮
│ id │ name │ depth │
╞════╪══════╪═══════╡
│  1 │ 教材 │     0 │
│  2 │ 通信 │     1 │
│  3 │ DB   │     1 │
│  4 │ TCP  │     2 │
│  5 │ UDP  │     2 │
│  6 │ SQL  │     2 │
╰────┴──────┴───────╯
3
WITH RECURSIVE walk(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=1 UNION ALL SELECT n.id,n.name,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.depth<1) SELECT * FROM walk ORDER BY depth,id;
╭────┬──────┬───────╮
│ id │ name │ depth │
╞════╪══════╪═══════╡
│  1 │ 教材 │     0 │
│  2 │ 通信 │     1 │
│  3 │ DB   │     1 │
╰────┴──────┴───────╯
4
WITH RECURSIVE walk(id,name,depth) AS (SELECT id,name,0 FROM nodes WHERE id=2 UNION ALL SELECT n.id,n.name,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id) SELECT * FROM walk ORDER BY depth,id;
╭────┬──────┬───────╮
│ id │ name │ depth │
╞════╪══════╪═══════╡
│  2 │ 通信 │     0 │
│  4 │ TCP  │     1 │
│  5 │ UDP  │     1 │
╰────┴──────┴───────╯
5
WITH RECURSIVE ancestors(id,name,parent_id,depth) AS (SELECT id,name,parent_id,0 FROM nodes WHERE id=4 UNION ALL SELECT n.id,n.name,n.parent_id,a.depth+1 FROM nodes AS n JOIN ancestors AS a ON n.id=a.parent_id) SELECT id,name,depth FROM ancestors ORDER BY depth;
╭────┬──────┬───────╮
│ id │ name │ depth │
╞════╪══════╪═══════╡
│  4 │ TCP  │     0 │
│  2 │ 通信 │     1 │
│  1 │ 教材 │     2 │
╰────┴──────┴───────╯
6
UPDATE nodes SET parent_id=4 WHERE id=1; SELECT id,parent_id FROM nodes WHERE id IN (1,2,4) ORDER BY id;
╭────┬───────────╮
│ id │ parent_id │
╞════╪═══════════╡
│  1 │         4 │
│  2 │         1 │
│  4 │         2 │
╰────┴───────────╯
7
WITH RECURSIVE reach(id) AS (SELECT 1 UNION SELECT n.id FROM nodes AS n JOIN reach AS r ON n.parent_id=r.id) SELECT id FROM reach ORDER BY id;
╭────╮
│ id │
╞════╡
│  1 │
│  2 │
│  3 │
│  4 │
│  5 │
│  6 │
╰────╯
8
WITH RECURSIVE walk(id,path,cycle) AS (SELECT 1,'/1/',0 UNION ALL SELECT n.id,w.path||n.id||'/',instr(w.path,'/'||n.id||'/')>0 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.cycle=0) SELECT id,path,cycle FROM walk ORDER BY path;
╭────┬───────────┬───────╮
│ id │   path    │ cycle │
╞════╪═══════════╪═══════╡
│  1 │ /1/       │     0 │
│  2 │ /1/2/     │     0 │
│  4 │ /1/2/4/   │     0 │
│  1 │ /1/2/4/1/ │     1 │
│  5 │ /1/2/5/   │     0 │
│  3 │ /1/3/     │     0 │
│  6 │ /1/3/6/   │     0 │
╰────┴───────────┴───────╯
9
WITH RECURSIVE walk(id,path,cycle) AS (SELECT 1,'/1/',0 UNION ALL SELECT n.id,w.path||n.id||'/',instr(w.path,'/'||n.id||'/')>0 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id WHERE w.cycle=0) SELECT id,path FROM walk WHERE cycle=1;
╭────┬───────────╮
│ id │   path    │
╞════╪═══════════╡
│  1 │ /1/2/4/1/ │
╰────┴───────────╯
10
UPDATE nodes SET parent_id=NULL WHERE id=1; WITH RECURSIVE walk(id,depth) AS (SELECT id,0 FROM nodes WHERE parent_id IS NULL UNION ALL SELECT n.id,w.depth+1 FROM nodes AS n JOIN walk AS w ON n.parent_id=w.id) SELECT COUNT(*) AS nodes,MAX(depth) AS max_depth FROM walk;
╭───────┬───────────╮
│ nodes │ max_depth │
╞═══════╪═══════════╡
│     6 │         2 │
╰───────┴───────────╯

演習完了