勉強日記

チラ裏

SQL Antipatterns ch3 Naive Trees

RDB SQL 勉強メモ

pragprog.com

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

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

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テーブル
  • ノードの複数の木に所属させたりできる