どうも、シローです。
今回は閉包テーブルって何か、どういう時に使うかを伝えたいと思います。
閉包テーブルとは
閉包テーブルとは自己参照型のデータの参照部分を切り出したテーブルのことを言います。
具体的にはLINEのチャットでコメントに対するリプライの関係性を格納します。
ER図
コメントのデータ自体を管理するのがCommentsテーブルで
コメントの祖先(ancestor)と子孫(descendant)を管理するのがTreePathsテーブルです。
TreePathsテーブルにはCommentsテーブルへの二つの外部キー(ancestor, descendant)を持っているのがポイントです。
ツリー構造を持つコメントデータの管理する場合
あるコメントに対してのリプライをできる機能を持つサービスで以下のようなツリー構造のコメントがあったとします。
これを閉包テーブルで表現すると。
Commentsテーブル
comment_id | user_id | message |
1 | 1 | 今日何食べた? |
2 | 2 | 焼肉 |
3 | 1 | いいね |
4 | 3 | 高級寿司 |
5 | 1 | うらやましいな |
6 | 2 | 自分も食べたいな |
TreePathsテーブル
ancestor | descendant |
1 | 1 |
1 | 2 |
1 | 3 |
1 | 4 |
1 | 5 |
1 | 6 |
2 | 2 |
2 | 3 |
3 | 3 |
4 | 4 |
4 | 5 |
4 | 6 |
5 | 5 |
6 | 6 |
ancestorには祖先としての自分自身のcomment_idを入れて、descendantにはその子孫に当たるcomment_idを入れています。
ツリー構造への参照や更新がしやすくなる
このような閉包テーブルでコメント間の親子関係を保存しておくことで、いろんな要件を満たしたクエリ実行が簡単になります。
comment_id=1をスレッドとして、その子に当たるコメントを全て取得する場合
SELECT c.* FROM Comments c INNER JOIN TreePaths t ON c.comment_id = t.descendant WHERE t.ancestor = 1;
comment_id=3を親とするコメント(comment_id=7)を新規追加したい場合
1 2 3 4 5 |
INSERT INTO TreePaths(ancestor, descendant) VALUES SELECT t.ancestor, 7 FROM TreePaths as t WHERE t.descendant = 3; INSERT INTO TreePaths(ancestor, descendant) VALUES (7,7); |
この場合だと(ancestor, descendant)=(1,7),(2,7),(3,7),(7,7)のデータが作成される。
comment_id=4を削除したい場合
1 2 3 4 |
DELETE FROM TreePaths WHERE decendant IN 4; DELETE FROM TreePaths WHERE ancestor IN 4; |
4は非葉ノード(中間の要素)なので、自身を子孫にもつレコードと自身を祖先に持つレコードを削除する。
この場合だと、(ancestor, descendant)=(1,4)(4,4)(4,5)(4,6)に当たる。
comment_id=4配下のコメントをcomment_id=2の配下に移動したい場合
図で表すと
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// 4の子孫と4の祖先の組み合わせからで自身を参照するものを除いたレコードを削除する DELETE FROM TreePath WHERE descendant IN ( SELECT descendant FROM TreePaths WHERE ancestor = 4; ) AND ancestor IN ( SELECT ancestor FROM TreePaths WHERE descendant = 4 AND ancestor != descendant; ); // 移動先の2の祖先と4の子孫の組み合わせを表す行を追加する INSERT INTO TreePaths(ancestor, descendant) SELECT supertree.ancestor = subtree.descendant FROM TreePaths AS supertree CROSS JOIN TreePaths AS subtree WHERE supertree.descendant = 2 AND subtree.ancestor = 4; |
難しいですが、まず4の子孫(4,5,6)を子孫に持つレコード(1,4)(1,5)(1,6)(4,4)(4,5)(4,6)(5,5)(6,6)と4の祖先かつ自分自身を参照しないレコードの祖先(1)を祖先にもつレコードは(1,4)(1,5)(1,6)の共通項は
(1,4)(1,5)(1,6)でこれを削除した後
移動先の2の祖先(1,2)と4の子孫(4,5,6)をクロス結合したレコード(1,4)(1,5)(1,6)(2,4)(2,5)(2,6)を追加します。
ただし、直近の親や子に絞って取得するのは難しくなる模様
閉包テーブルでは、あるコメントの直近の子や親を直接取得するのは難しいです。
解決策として、パスの長さを保存するというのがあります。
経路の長さ付きの閉包テーブル
int | ancestor |
int | descendant |
int | path_length |
サンプルデータ
ancestor | descendant | path_lengths |
1 | 1 | 0 |
1 | 2 | 1 |
1 | 3 | 2 |
1 | 4 | 1 |
1 | 5 | 2 |
1 | 6 | 2 |
2 | 2 | 0 |
2 | 3 | 1 |
3 | 3 | 0 |
4 | 4 | 0 |
4 | 5 | 1 |
4 | 6 | 1 |
5 | 5 | 0 |
6 | 6 | 0 |
ただ、まあなんというのでしょう・・
ツリーの更新のたびに長さも一緒に更新しないといけなくなって、それはそれで大変なんだよなぁ
疲れた、この辺でいいや
まとめ
- ツリー型のデータ構造を表す手段として閉包テーブルがある。
- 閉包テーブルは祖先と子孫のペアを格納するテーブルである。
- ツリーの更新が閉包テーブルのみで完結する。
- ただし、直近の親と子を取得するのが難しくなる。
ちょー疲れた、頭使ったわ
本書はDB設計やSQL記述の際に避けるべき事柄を1章で1つ、25個紹介する書籍です。
リレーショナルデータベースを中心に据えたシステム開発には、様々な場面で陥りやすい失敗(アンチパターン)があります。
本書はデータベース論理設計、データベース物理設計、クエリの記述、アプリケーション開発という4つのカテゴリに分かれて、それぞれの分野におけるアンチパターンを紹介し、失敗を避けるためのより良い方法を紹介します。
複数の値を持つ属性や再帰的なツリー構造の格納から、小数値の丸めやNULLの扱いに起因する問題、全文検索やSQLインジェクション、MVCアーキテクチャなど、実践的かつ幅広いトピックを網羅します。
データベースに関わるすべてのエンジニア必携の一冊です。