再帰クエリ（WITH RECURSIVE）：階層とグラフ

WITH RECURSIVEで木とグラフをたどり、深さの計算とサイクルの検出を使いこなしましょう。

11 分 · 3 問

再帰CTEは、UNION ALLでつながれた二つの部分からなります。開始行を与えるアンカー項と、CTE自身を参照する再帰項です。SQLiteはアンカーを一度実行し、それから新しい行に対して再帰項をループで適用し、行が生まれなくなるまで続けます。それを説明するために、マネージャーの階層を作りましょう。

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

Adaの下の組織図を展開するために、アンカーは深さ0でルートを選び、再帰項は各従業員を、すでにCTEに存在するそのマネージャーに結合しながら、深さを1ずつ増やします。自分で計算するdepth列は、階層の段階を測る最もシンプルな方法です。

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

グラフは辺のテーブル(src, dst)でモデル化されます。たどり方は同じ仕組みですが、グラフはサイクルを含むことがあります。1 -> 2 -> 3 -> 1をたどると永遠にループします。対策は、たどった経路をテキスト列に覚えておき、すでに訪れたノードを拒否することです。instr関数は、その経路の中で二つのドットに挟まれたノードを探します。

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

理解度チェック

このレッスンの要点をしっかり覚えているか確認しましょう。

1. 再帰CTEで、アンカー項と再帰項をつなぐ演算子はどれですか？
   • UNION ALL（またはUNION）
   • JOIN
   • INTERSECT
   • CROSS APPLY
2. 循環のあるグラフは、なぜUNION ALLで無限再帰の恐れがあるのですか？
   • UNION ALLが結果を必ずソートするから
   • 同じノードが重複除去なしに再訪されるから
   • SQLiteが再帰のあいだインデックスを無効にするから
   • アンカーが毎回再評価されるから
3. SQLiteで循環のあるグラフをたどるとき、どうやって無限ループを避けますか？
   • 再帰項にORDER BYを加える
   • たどった経路を覚えておき、すでに訪れたノードを除外する
   • 標準のCYCLE句を使う
   • メモリキャッシュのサイズを増やす