階層型データ構造
一つの親を持ち、一つ以上の子を持つような階層型データはよくあると思います。
しかし、あまり深く考えずに設計してしまうと、あとあとうまくSQLが書けなくて困ったりします ( 自分は困りました )。
「SQLアンチパターン」の第2章にこのような階層型データの格納について詳しく載っていたので、簡単にまとめてみました。
「SQLアンチパターン」にはそれぞれの長所と短所についてより詳しく解説してありますので、もっと知りたい方は読んでみることをお勧めします。
案その1: 隣接リスト
parent_id などの名前で、同じテーブル内の別の行を参照する方法です。
私自身も目にしたことがある、よくある方法だと思います。
実際の業務で行うかは別にして、下記のように外部キー制約をつけることもできます。
CREATE TABLE Users (
id SERIAL PRIMARY KRY,
parent_id BIGINT UNSIGNED,
name VARCHAR(255),
FOREIGN KEY (parent_id) REFERENCES Users(id),
);
長所
- 直近の子供の取得が簡単
- 子供の追加が簡単
- 親の変更が簡単
- 参照整合性を維持できる
- 再帰クエリがサポートされているデータベース製品なら無問題
短所
- すべての子孫、先祖を取得するクエリを書くのが困難 ( どう頑張っても非効率 )
- すべての子孫の削除が困難 ( 外部キー制約時に ON DELETE CASCADE を付ければできる )
- 子供の削除の際にそのさらに子供を昇格させるのが面倒
案その2: 経路列挙 (Path Enumeration, Materialized Path)
UNIX のパス /usr/local/lib/ は、ファイルシステムの経路列挙です。 usr が local の親、ということですね。
これを先ほどの Users テーブルに当てはめるには、 parent_id 列の代わりに path という列を大きめの VARCHAR として定義します。
長所
- すべての子孫や先祖の取得や削除が容易
- 子供の追加も行える ( 案その1の方が楽 )
短所
- 無効なパスをデータベースが検出できない ( アプリケーションコード頼みになる )
- パスの長さに制限がある。
案その3: 入れ子集合 ( Nested Set )
直近の親ではなく、子孫の集合に関する情報を nsleft, nsright という数値で管理する方法です。
nsleft にはそのすべての子孫の値よりも小さな値が、 nsright にはそのすべての子孫の値より大きな値が入ります。この値は id とは関係ありません。
正直個人的にこの方法はかなり頭を捻らないとクエリを書くことが難しいと感じました。慣れるまで大変だと思います。
長所
- とある子供を削除すると、そのまた子供が削除された親の子供だと自動的にみなされる ( 長所となるかは仕様によります。ある意味要注意です。)
短所
- 直近の親子へのクエリ実行が煩雑
- 子供の追加や親の変更が複雑
- 削除が難しい
案その4: 閉包テーブル ( Closure Table )
閉包テーブルは、直接の親子関係だけではなく、階層全体のパスを格納します。
先ほど例に挙げた Users テーブルに加えて、TreePaths テーブルを新たに定義します。
下記のように、外部キー制約をつけることもできます ( 実際の業務で行うかは別として ) 。
このテーブルの各行には先祖、子孫関係の組み合わせをすべて格納します。
また、自分自身を参照する行も追加します。
CREATE TABLE Users (
id SERIAL PRIMARY KRY,
name VARCHAR(255),
);
CREATE TABLE TreePaths (
ancestor BIGINT UNSIGNED NOT NULL,
descendant BIGINT UNSIGNED NOT NULL,
PRIMARY KEY (ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES Users(id),
FOREIGN KEY (descendant) REFERENCES Users(id)
);
また、この方法に関しては、下記のサイトで詳しく述べられていたので参考になるかと思います。
https://enomotodev.hatenablog.com/entry/2015/11/19/235300
長所
- 先祖や子孫の取得が容易
- 新しい行の挿入が容易
- 一行の削除が容易
- ツリー全体の削除が容易
- 構造を削除してもデータそのものは消えない ( 要注意 )
- 参照整合性の維持が可能
短所
- 構造を削除してもデータそのものは消えない ( 要注意 )
- テーブルが二つになる ( ロックなど注意が必要 )
- 階層が深くなると多くの行数が必要になる
個人的な所感
直接の子供と親だけを取得できれば十分な場合は、「隣接リスト」がもっともわかりやすく、馴染みがあるため採用されやすいと思います。
しかし、すべての子孫や先祖など、「ツリーへのクエリの実行」が必要なのであれば、「閉包テーブル」がもっとも優れているのではないでしょうか。「経路列挙」でもツリーへのクエリの実行は可能ですが、上で記した短所のことを考えると「閉包テーブル」に軍配が上がりそうです。
ただ、どの方法をとったとしても階層関係を表現するのは簡単ではないと感じました。先ほど優れていると述べた閉包テーブルに関しても、デメリットがないわけではないですし、親子の循環関係などをデータベース制約で防ぐことはできません。
割とよくある階層型データの格納ですが、かなりの覚悟を持って挑む必要がありそうです。