SQL

SQL:閉包テーブルってなんぞや

どうも、シローです。

今回は閉包テーブルって何か、どういう時に使うかを伝えたいと思います。

閉包テーブルとは

閉包テーブルとは自己参照型のデータの参照部分を切り出したテーブルのことを言います。

具体的には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)を新規追加したい場合

この場合だと(ancestor, descendant)=(1,7),(2,7),(3,7),(7,7)のデータが作成される。

comment_id=4を削除したい場合

4は非葉ノード(中間の要素)なので、自身を子孫にもつレコードと自身を祖先に持つレコードを削除する。

この場合だと、(ancestor, descendant)=(1,4)(4,4)(4,5)(4,6)に当たる。

comment_id=4配下のコメントをcomment_id=2の配下に移動したい場合

図で表すと

難しいですが、まず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

ただ、まあなんというのでしょう・・
ツリーの更新のたびに長さも一緒に更新しないといけなくなって、それはそれで大変なんだよなぁ

 

疲れた、この辺でいいや

 

まとめ

  • ツリー型のデータ構造を表す手段として閉包テーブルがある。
  • 閉包テーブルは祖先と子孫のペアを格納するテーブルである。
  • ツリーの更新が閉包テーブルのみで完結する。
  • ただし、直近の親と子を取得するのが難しくなる。

ちょー疲れた、頭使ったわ

 

SQLアンチパターン

本書はDB設計やSQL記述の際に避けるべき事柄を1章で1つ、25個紹介する書籍です。
リレーショナルデータベースを中心に据えたシステム開発には、様々な場面で陥りやすい失敗(アンチパターン)があります。
本書はデータベース論理設計、データベース物理設計、クエリの記述、アプリケーション開発という4つのカテゴリに分かれて、それぞれの分野におけるアンチパターンを紹介し、失敗を避けるためのより良い方法を紹介します。
複数の値を持つ属性や再帰的なツリー構造の格納から、小数値の丸めやNULLの扱いに起因する問題、全文検索やSQLインジェクション、MVCアーキテクチャなど、実践的かつ幅広いトピックを網羅します。
データベースに関わるすべてのエンジニア必携の一冊です。
  • この記事を書いた人

シロー

Webシステムの開発のお仕事をさせて頂いております。 フリーランスの日常、Web開発に関する情報を発信しています。 趣味はゲーム、映画鑑賞、個人サービスを作ることです。

-SQL

© 2021 Shiro's secret base