Closure Table（クロージャ・テーブル）徹底ガイド：SQLで階層・DAGを高速に扱う設計・実装・運用ポイント
エバープレイ編集部Closure Table とは
Closure Table（クロージャ・テーブル）は、リレーショナルデータベースでツリーや有向非巡回グラフ（DAG）のような階層構造を効率的に扱うための設計パターンの一つです。各ノード同士の「到達可能性（ancestor → descendant）」を明示的に表すトランジティブ・クロージャ（transitive closure）をテーブルとして持つことで、祖先・子孫の検索を単一の結合（JOIN）で高速に行えるようにします。
基本構造とスキーマ
一般的な Closure Table のスキーマは、少なくとも 2 つのテーブルを持ちます。
- nodes（ノード情報、id や名前など）
- closure（ancestor, descendant, depth などを持つ表）
closure テーブルの典型的なカラムは次の通りです。
- ancestor: 祖先ノードの id
- descendant: 子孫ノードの id
- depth: 祖先から子孫までの距離（自己関係で 0）
主キーは (ancestor, descendant) にし、検索パフォーマンスのために descendant や ancestor に別途インデックスを張るのが普通です。nodes.id に対する外部キー制約を設定することも可能で、整合性をDBに委ねられます。
なぜ Closure Table を使うのか（利点）
- 祖先・子孫・パス・深さ（depth）などの取得が単一の結合で高速にできる（read に強い）。
- 複数親を持つ DAG をそのまま扱える（厳密な木だけでなくグラフにも適用できる）。
- SQL だけで最短共通祖先（LCA）やパスの組み立て、部分木の取得が可能。
- ノードの移動（サブツリー移動）や挿入・削除のアルゴリズムが比較的素直（ネスト集合法のような大規模な再計算が不要）。
- 参照制約やトランザクションを使って一貫性を保ちやすい。
欠点と注意点
- データサイズの増加：最悪でノード数 N に対し O(N^2) の行数になる可能性がある（線形チェーンだと N(N+1)/2）。
- 書き込みコスト：ノードの追加・削除・移動時に closure テーブルの複数行を挿入／削除する必要がある。
- 循環（サイクル）を許す設計の場合は無限ループ的な問題が生じるため、サイクル対策（チェック）を実装する必要がある。
代表的な操作と SQL 例
以下では例として nodes(id, name) と closure(ancestor, descendant, depth) を使います。SQL は概念的なサンプルで、DBMS により若干の文法差異（DELETE の JOIN 文法など）がある点に注意してください。
ノード挿入（親を指定して新ノードを追加）
親 parent_id の下に新しいノード new_id を追加する場合、closure テーブルには「親のすべての祖先 → 新ノード」関係を追加し、さらに新ノード自身の自己参照（new_id → new_id, depth=0）を入れます。
INSERT INTO closure (ancestor, descendant, depth)
SELECT ancestor, :new_id, depth + 1
FROM closure
WHERE descendant = :parent_id
UNION ALL
SELECT :new_id, :new_id, 0;子孫（部分木）の取得
あるノード x のすべての子孫を depth 順に取得する例：
SELECT n.*, c.depth
FROM nodes n
JOIN closure c ON n.id = c.descendant
WHERE c.ancestor = :x AND c.depth > 0
ORDER BY c.depth;祖先の取得（ルート方向へ）
SELECT n.*, c.depth
FROM nodes n
JOIN closure c ON n.id = c.ancestor
WHERE c.descendant = :x
ORDER BY c.depth DESC;パスを文字列で取得（MySQL の GROUP_CONCAT / PostgreSQL の string_agg）
-- MySQL の例
SELECT GROUP_CONCAT(n.name ORDER BY c.depth DESC SEPARATOR ' / ') AS path
FROM closure c
JOIN nodes n ON n.id = c.ancestor
WHERE c.descendant = :x;サブツリーの移動（ノード x を親 y の下へ移動）
アルゴリズム概略：
- x の全ての descendants（サブツリー）と x の全ての ancestors を一時集合として取得。
- サブツリーの外側にある anc→desc 関係（移動前の古い祖先とサブツリーの末尾を結ぶ行）を削除。
- 新しい親 y の祖先群とサブツリーの各ノードを組み合わせて新しい closure 行を挿入。
SQL（概念例、DB により調整が必要）：
-- 削除（古い anc->sub のリンクを削除）
DELETE FROM closure
WHERE descendant IN (SELECT descendant FROM closure WHERE ancestor = :x)
AND ancestor IN (SELECT ancestor FROM closure WHERE descendant = :x AND ancestor != :x);
-- 挿入（newParent の祖先 × サブツリーの全 descendants を追加）
INSERT INTO closure (ancestor, descendant, depth)
SELECT super.ancestor, sub.descendant, super.depth + sub.depth + 1
FROM closure AS super
JOIN closure AS sub ON sub.ancestor = :x
WHERE super.descendant = :new_parent;実運用では一時テーブルを使う、トランザクションで整合性を確保する、サイクル検査を行う、などの実装上の工夫が必要です。
パフォーマンスと複雑度
読み取り（SELECT）に関しては closure テーブルは非常に効率的です。祖先・子孫・深さなどの問い合わせが単一のインデックススキャン＋JOINで済むため、特に頻繁に読まれる階層データに向きます。一方、書き込み（INSERT/DELETE/MOVE）は影響範囲の closure 行数に比例して遅くなります。
空間的な複雑度はツリーの構造に依存します。完全 k 分木などでは行数は O(N log_k N) 程度になることもありますが、最悪の連結リスト状（深いチェーン）では O(N^2) の closure 行数になる点に注意してください。
ネスト集合法（Nested Sets）や再帰CTE（Adjacency List + WITH RECURSIVE）との比較
- Adjacency List + WITH RECURSIVE：書き込みは軽いが、深い木・頻繁な集計・LCA などは再帰クエリが必要でコストがかかる。DB が recursive CTE をサポートしていれば単純に実装可能（PostgreSQL, MySQL 8+, SQL Server 等）。
- Nested Sets（左・右値法, MPTT）：読み取りで部分木を効率的に取得できるが、ノード挿入や移動時に多くの行を再計算（左・右値の更新）する必要がある。
- Closure Table：読み取りが高速かつ柔軟、複数親を扱える点や LCA を取りやすい。一方で closure のストレージと書き込みコストをトレードオフする設計。
運用上の実務的なポイント
- インデックス設計：少なくとも (ancestor, descendant) を主キーに、(descendant) にもインデックスを張る。
- トランザクション：挿入・削除・移動の一連操作はトランザクションで囲み、一貫性を保つ。
- トリガーやストアドプロシージャ：アプリ層ではなく DB 層で closure の更新を自動化するとミスが減る。
- サイクル検査：DAG やツリーを期待する場合、追加時に ancestor になりうるノードの集合に descendant が含まれていないかをチェックする。
- パーティショニングやアーカイブ：巨大な closure テーブルになる場合、古いデータのアーカイブやパーティション分割を検討する。
ユースケース
- カテゴリ／タグ階層（EC の商品カテゴリなど）
- 組織図（社員の上司体系）
- 権限伝播（ある権限が親から子へ伝播するケースの判定）
- 依存関係（ビルド依存、タスク依存など）を表す DAG
まとめ
Closure Table は「読み取りを高速に、柔軟に」したい場面で非常に有効なパターンです。特に頻繁に祖先・子孫・パス・LCA を問い合わせるシステムでは優れた選択肢になります。一方でデータ量の増加や書き込み時の更新コストが課題なので、構造の特性（木か DAG か、平均深さ、書き込み頻度）を考慮して、再帰CTE やネスト集合法など他の手法と比較検討することが重要です。
参考文献
- Managing Hierarchical Data in MySQL — Mike Hillyer（階層データの代表的な解説、ネスト集合やその他手法の比較）
- Transitive closure — Wikipedia（トランジティブ・クロージャの数学的背景）
- Stack Overflow: What are advantages of closure table over nested sets?（実装差や利点の議論）
- PostgreSQL: WITH (Common Table Expressions) — Documentation（再帰CTE の仕様と例）
- MySQL 8.0: WITH (Common Table Expressions) — Documentation（MySQL の再帰CTE）
投稿者プロフィール
