閉包テーブルとは
閉包テーブル（Closure Table）は階層構造のシンプルかつエレガントな格納方法です。
閉包テーブルは親子関係だけではなく、ツリー全体のパスを格納します。
参考：SQLアンチパターン 2.5.3 閉包テーブル（Closure Table）
ディレクトリのような階層構造をテーブルで表現するときに、階層構造の情報だけを持つ新たなテーブルを定義する技法です。
はじめに
前提
突然ですが、図のような階層構造をテーブルで表現する場合、どのような設計にするでしょうか？
ぱっと思いつくのは以下のような設計で自己結合を行うことですが...
これは「隣接リスト」と呼ばれる設計で、特定の条件を満たさない場合アンチパターンに該当します。
なぜアンチパターンになるかわからない方、本記事一読の価値ありです！
大まかな流れ
本記事では以下について記述します。
なぜ隣接リストがアンチパターンになるのか
１．すべての子孫を取得する
ID＝１のディレクトリからすべての子孫ディレクトリを取得するケースを考えます。
隣接リストでは直近の親子関係のみを保持しているため、すべての子孫を取得するためには階層数分のJOINが必要になります。
SELECT d1.id, d2.id, d3.id, d4.id
FROM `directories` d1 --1階層目
LEFT OUTER JOIN directories d2 --2階層目
ON d2.parent_id = d1.id
LEFT OUTER JOIN directories d3 --3階層目
ON d3.parent_id = d2.id
LEFT OUTER JOIN directories d4 --4階層目
ON d4.parent_id = d3.id
WHERE d1.id = 1;
4階層目までを取得することができますが、仮に5階層目が追加された場合に5階層目は取得されません。
また、2階層目までだけを取得したい場合にも、4階層目までの無駄なJOINが発生します。
ディレクトリの性質上、階層はどんどん深くなりますし、事前に深さが決まっていることはないと思います。
階層の深さに伴ってJOINの数を変更する必要があり、イケてないことは明らかです
２．自ディレクトリまでの経路を取得する
ルートディレクトリからID＝４のディレクトリまでの経路を取得するケースを考えます。
こちらも階層数分のJOINを行う必要があります。
また、こちらも階層数が固定されている場合しか使用できないSQLになってしまっています...。
SELECT d1.id, d2.id, d3.id, d4.id, d4.content
FROM `directories` d4
LEFT OUTER JOIN directories d3
ON d4.parent_id = d3.id
LEFT OUTER JOIN directories d2
ON d3.parent_id = d2.id
LEFT OUTER JOIN directories d1
ON d2.parent_id = d1.id
WHERE d4.id = 4;
以上から隣接リストには以下のようなデメリットがあることがわかります。
- 階層構造全体の情報を取得するクエリをうまく書くことができない
- 階層数がわかっていないとSQLを書けない
- 階層数が異なれば別にSQLを用意しなくてはならない
閉包テーブルを使用してみる
閉包テーブルの作り方
先に書いた通り、閉包テーブルは「階層構造の情報だけを持つ新たなテーブルを定義」します。
具体的には元のテーブル設計に以下の変更を行います。
-
directoriesテーブルでは関連にあたるparent_idを保持しない - 階層構造全体の親子関係を格納する
directory_relationsテーブルを作成する
このときdirectory_relationsテーブルには直近の親子関係だけではなく、すべての親子関係を保持させます（自身を含む）。
したがってdirectory_relationsテーブルに持たせるレコードは以下の通りになります。
| parent_id | child_id |
|---|---|
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 1 | 4 |
| 1 | 5 |
| 1 | 6 |
| 1 | 7 |
| 1 | 8 |
| 2 | 2 |
| 2 | 3 |
| 2 | 4 |
| 3 | 3 |
| 3 | 4 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 6 | 7 |
| 7 | 7 |
| 8 | 8 |
１．すべての子孫を取得する
ID＝１のディレクトリからすべての子孫ディレクトリを取得するケースを考えます。
directory_relationsは直近以外の親子関係もすべて保持しているため、parent_id=1のディレクトリを取得するだけで済みます！
また、階層の深さに関わらず自分の子孫ディレクトリすべての情報を保持するため、ディレクトリが何階層になろうがこのSQLで取得することができます。
SELECT parent_id, child_id
FROM `directory_relations`
WHERE parent_id = 1;
２．自ディレクトリまでの経路を取得する
ルートディレクトリからID＝４のディレクトリまでの経路を取得するケースを考えます。
こちらも階層構造のテーブルからchild_id=4のものをすべてSELECTするだけで済みます。
SELECT parent_id, child_id
FROM `directory_relations`
WHERE child_id = 4;
閉包テーブルのメリットとデメリット
隣接リストと比較した閉包テーブルのメリットとデメリットを挙げます。
閉包テーブルのメリット
- 階層構造に対してのクエリ実行が容易になる
これまでで見てきた通り、階層構造の取得が短いSQLで書けるようになります。
また階層の増減にも強く、統一的なSQLで様々な深さの階層構造を取得することができます。
閉包テーブルのデメリット
- カラムの追加・変更（他ディレクトリへの付け替え）が少し難しくなる
隣接リストでは単に新たなディレクトリレコードを追加すればいいだけです。
閉包テーブルを採用した場合はディレクトリ追加のたびに閉包テーブルへのレコード追加が発生します。
特に変更の場合・変更したディレクトリの階層が深い場合更新するレコードの数もそれなりに多くなります。
- ディレクトリ階層が深くなると閉包テーブルのレコード数が膨大になること
計算が楽になる文、スペースが消費されてしまうというトレードオフが生じます。
とはいえDBの容量が増えた現代では問題になることが少なく、上記のメリットに比較して些細なデメリットであるように思えます。
隣接リストを使用してよいケース
アプリケーション要件に適している場合
隣接リストの長所は直近の親と子を簡単に取得できること・列の挿入や削除が閉包テーブルを使用した場合に比べ容易であることです。
当然ですが、要件として「階層構造の全体を取得する必要がない（＝直近の親子関係のみ取得できれば十分である）場合」隣接リストには何の問題もありません。
DBが再帰クエリをサポートしている場合
再帰クエリ (英: recursive query) もしくは 階層クエリ (英: hierarchical query) は、再帰的な問い合わせを行う SELECT ステートメントである。
階層構造を持つデータなどに使う。
再帰クエリは前に行った処理の結果を利用して同じ処理を繰り返す場合に使われます。
再帰クエリを使用すれば隣接リスト設計でも深い階層構造を統一的なSQLで取得することが可能で、この場合も隣接リストはアンチパターンではなくなります。
※MySQLは8.0から再帰クエリをサポートしているようで、5.6などでは使用できないようです...
再帰クエリについては本旨から外れますので割愛しますが、@Shoyu_N様の以下の記事がわかりやすかったので引用させていただきます。
おわりに
SQLアンチパターンでは隣接リストの問題を解決する手法のうちの一つとして紹介されており、他にも「経路列挙」「入れ子集合」などの解決方法が紹介されています。
当記事も「階層構造が来たら閉包テーブルだ！」というものではなく手法の一つとして紹介するものになります。
結局はアプリケーション要件に合わせて適切な方法を選択することが大事だと思います。
まずは取り得る選択肢を知らないとどうにもならないと思うので、アンチパターンと合わせて色々な設計技法を覚えていきたいところです