SQL Antipatterns ch3 Naive Trees

RDB SQL 勉強メモ

出典:

https://pragprog.com/book/bksqla/sql-antipatterns

A hierarchy consists of entries and relationships. Model both of these to suit your work.

Naive Trees

再帰データ構造をSQLで表現
- 例: コメントの返信スレッド

comment_id	parent_id	comment
…

すぐ思いつくこの構造には問題がある
- 長いコメントチェーンを1クエリで取得するのが困難
  - 子の取得はJOIN
  - コメントチェーンの長さは無制限
  - SQLのJOIN数は固定長
- 全エントリ取得してアプリケーション側で木を構築するのも計算量・リソース的に非現実

Objective: Store and Query Hierarchies

データに再帰関連をもたせるのは普遍的なアイデア
木
- ノード
  - エントリ
- ルート
  - 親のないエントリ
- リーフノード
  - 子のないエントリ
- ノンリーフノード
  - 中間のノード
木構造データの例
- 組織図
- コメント返信スレッド

Antipattern: Always Depend on One’s Parent

@startuml
class 1
class 2
class 3
class 4
class 5
class 6
class 7

1 -- 2
2 -- 3
1 -- 4
4 -- 5
4 -- 6
6 -- 7
@enduml

tree

隣接リスト

comment_id	parent_id	author	comment
1	NULL	Fran	What’s the cause of this bug?
2	1	Ollie	I think it’s a null pointer.
3	2	Fran	No, I checked for that.
4	1	Kukla	We neet to check for invalid input.
5	4	Ollie	Yes, that’s a bug.
6	4	Fran	Yes, please add a check.
7	6	Kukla	That fixed it.

Query a Tree with Adjacency List

JOIN句では固定の深さまでしかデータを取得できない
全データ取得してアプリケーション側で木を構築するのも非効率
- 部分木で十分
- 必要なのはレコードの中身ではなく集約した結果のみ
  - COUNT()とか

Mantaining a Tree with Adjacency List

いくつかの操作は単純に実現できる
- 葉ノードの追加
- 単ノードや部分木の再配置
削除は複雑
1. 部分木のノードを特定
2. 葉側から順に削除
  - FK制約違反をさけるため
  - 子孫を昇格したり再配置したりしないならばON DELETE CASCADEで自動化できる

How to Recognize the Antipatterns

こんなのが聞こえてきたら注意
- 「木の深さはどれだけ深くまでサポートすればいい？」
  - 全子孫を取得できないから生じる質問
- 「木構造を管理するコードを触るのが怖い」
  - しんどい方法を選んでしまった
- 「孤立したノードを掃除するためにスクリプトを定期実行する必要がある」
  - ノンリーフノードを削除した時に孤立ノードが生ずる
  - 後述の方法 + トリガー・FK制約のカスケーディングを用いることで弾力性をもたせることができる

Legitimate Uses of the Antipattern

隣接リスト方式の強み
- あるノードの直接の親/子を容易に取得
- 列の追加が容易
操作がこれだけならうまくいくだろう
再帰クエリがあればそれを使える
- MySQLにはない

Don’t Over-Engineer

「任意の深さの木構造データを扱えるよう」
子が1世代しかないことに顧客が気づかず
任意の深さの木構造データを扱えるものを何週間もかけて作ってしまった

Solution: Use Alternative Tree Models

他の使え
- パス列挙
- 入れ子集合
- クロージャテーブル
他の書籍で散々やったので省略

Which Design Should You Use?

設計	テーブル数	子取得	部分木取得	INSERT	DELETE	参照整合性
隣接リスト	1	easy	hard	easy	easy	yes
再帰クエリ	1	easy	easy	easy	easy	yes
パス列挙	1	easy	easy	easy	easy	no
入れ子集合	1	hard	hard	hard	hard	no
クロージャテーブル	2	easy	easy	easy	easy	yes

クロージャテーブルのテーブル構成
- Nodesテーブル
- TreePathsテーブル
ノードの複数の木に所属させたりできる