SQLアンチパターン 2章
アンチパターン
この章ではツリー指向のデータ構造を格納する際のアンチパターンになります。
ツリー指向のデータ構造では、ノードは一つ以上の子ノード及び一つの親ノードを持ち一番上がルート、一番下がリーフとなります。文章だと難しいので視覚で、
このような構造です。ディレクトリなんかと同じ構造ですね。 この構造を格納するためにparent_idカラムをつくり格納すると以下のようになります。
| parts_id | parts_name | parent_id |
|---|---|---|
| 1 | SQLアンチパターン | |
| 2 | 一章 | 1 |
| 3 | 二章 | 1 |
| 4 | 一節 | 2 |
| 5 | 二節 | 2 |
| 6 | 一節 | 3 |
| 7 | 二節 | 3 |
| 8 | 一項 | 6 |
この構造は隣接リストと呼ばれています。これが今回のアンチパターンです。
デメリット
- 全ての子ノードを取得したい時に（例えば東京から下のノードをすべて取りたい時）に一つ下の子ノードしか辿れないので、一つ一つジョインしていくしかありません。これでは階層が深くなった時に対応できません。
- ノードの追加や移動は簡単ですが、削除するには削除したいノードの子ノードも全て探して削除しなければなりません。またノード単体を移動したいときも、子ノードは一つ上の親に依存しているので親ノードが移動すると子ノードとその下のノードは全てツリーが移動してしまいます。
使用してもいい場合
ノードの削除が要らなかったり親と子だけ別れば良いときには使用しても問題ありません。家系図なんかは追加はしても削除はしないので、使用しても問題はないと思います。
解決策
他のツリーモデルを利用することです。本では3つの構造があげられています。
経路列挙
| parts_id | parts_name | parent_path |
|---|---|---|
| 1 | SQLアンチパターン | |
| 2 | 一章 | 1 |
| 3 | 二章 | 1 |
| 4 | 一節 | 1/2 |
| 5 | 二節 | 1/2 |
| 6 | 一節 | 1/3 |
| 7 | 二節 | 1/3 |
| 8 | 一項 | 1/3/6 |
UNIXのパスと同じ形で上のツリーのノードを記録する構造です。 この構造のメリットは子ノードを簡単に取得できます。１/3/%といった形で一章の子ノードを階層がいくら深くても全て取得できます。
入れ子集合
| parts_id | parts_name | nsleft | nsright |
|---|---|---|---|
| 1 | SQLアンチパターン | 1 | 16 |
| 2 | 一章 | 2 | 7 |
| 3 | 二章 | 8 | 15 |
| 4 | 一節 | 3 | 4 |
| 5 | 二節 | 5 | 6 |
| 6 | 一節 | 9 | 12 |
| 7 | 二節 | 13 | 14 |
| 8 | 一項 | 10 | 11 |
子孫の集合に関する情報をそれぞれの行に入れています。
nsleftには下のノード全ての値より小さい値、nsrightには逆に下のノード全ての値より大きい値が入っています。
ノードAの下のノードを全て特定したいときはAの子ノードの範囲内にnsleftが入っているノードを検索することで達成できます。逆にAの上のノードを全て検索したいときはAのnsleftを範囲内に持つノードを検索することで取得できます。
またあるノードを削除しても子ノードや親ノードを検索することに不都合はなく、削除されたノードの子ノードは親の親ノードの子であるとみなされるので削除も容易です。
しかしノードの挿入や移動は他の構造より複雑になります、全てのノードが親だけに依存しているわけではないので移動するといちいち値の計算のし直しです。
閉包テーブル
| parant_id | child_id | parant_id | child_id | parant_id | child_id |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 5 | 5 |
| 1 | 2 | 2 | 4 | 6 | 6 |
| 1 | 3 | 2 | 5 | 6 | 8 |
| 1 | 4 | 3 | 3 | 7 | 7 |
| 1 | 5 | 3 | 6 | 8 | 8 |
| 1 | 6 | 3 | 7 | ||
| 1 | 7 | 3 | 8 | ||
| 1 | 8 | 4 | 4 |
テーブルの親と子の組み合わせを深さに関係なく全て格納するテーブルを作成する構造です。ノード自身を参照する組み合わせも格納します。前回の関係のためだけの中間テーブルに似ている気もします。
下のノード全てを検索するのは簡単でparant_idが4の組み合わせを取り出して元のテーブルをjoinすればいいです。先祖もchild_idから特定できます。
一ノードを追加するとその親とその上のノード全てを取得して新しいノードをchild_idとして登録することになります。削除では削除したいノードをchild_id持つ行を全て削除することになります。全て削除とかは機械は得意なのでいいですね。
もちろん閉包テーブルを削除しても章の情報は残ったままです。これはノードの関連付けを柔軟にできることにも繋がります。
どの設計を使うべきか
それぞれメリット・デメリットあります。
- アンチパターンとして挙げられた親ノードだけ持つ隣接リストは、下のノードがすぐわかればいい、削除等は基本行わないという用途に適していると思います。上記にも書きましたが家計なんかでしょうか。
- 親ノードまでの階層の道のりを全て持つ経路列挙は、道のりに変なものが入らない保証はできない、階層の深さに制限がかかる、といったデメリットがあります。住所なんかはパンくずリストから一気に参照したいことが多いでしょうし適していると思います。
- 子ノードの範囲を行に入れる入れ子集合は、削除はできますが挿入がしにくいです。ツリー構造の中のツリーを検索することが容易なので、本の分類なんか適していると思います。社会学とか数学とか分類は決まっていて、数学のツリーを見たいといった操作に適していると思うからです。
- 子ノード及びその下のノード全ての関係を別テーブルに保存しておく閉包テーブルは、検索や削除、挿入容易ですし、外部キー制約が使えるので整合性も良いですが、別のテーブルを使う、行数そのものは多くなるという欠点が生じます。これは用途というよりスペックの問題な気がします。
感想
この章はだいぶアルゴリズムを感じました。
調べる中でアルゴリズムの学習らしき論文っぽいものが多くでてきて、「これがアルゴリズムを学ぶことなのか」と感じました。実際SQLアンチパターンでも最後にアカデミックな資料をおすすめされています。
階層に対するクエリの実行だとかはデータベースとビューをつなぐ役割を持つバックエンドとしては必須の知識感ありますね（まだ全くないんですが…）
ここ理解違うんじゃない？みたいなのがあれば是非お願いします！