SQLアンチパターン ナイーブツリー

ナイーブツリー （素朴な木）

今回はナイーブツリー （素朴な木）について

隣接リストモデル。
ツリー構造を表現する際に直近の親のみを参照することでツリー構造を表現するアンチパターン。
以下のようなパターンが当てはまる。

comments

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
3	1	>>1 バーベキューしたい！
4	3	>>3 釣りもやりたい！
5	3	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

簡単に解説すると以下の通り。
「id.1」の投稿に対して「id.2」「id.3」「id.6」が返信。
「id.1」の投稿に対して返信した「id.3」に対して「id.4」「id.5」が返信している。

雑な図ですみません.....
上記の図だと親として扱われているのは「id.1」「id.3」となり、親に対する子要素はそれぞれ自分の親になるidを持っているためスレッド形式の掲示板を表現するのに問題ないように見える。

では、何が問題なのか見ていく。

デメリット

• ツリー全体、もしくはある要素のサブツリーが取得しづらい。
• 非葉ノードを削除した際に整合性を取りづらい。

大きくこのようなデメリットが存在。
詳しく解説していく。

ツリー構造の取得

１つ目のデメリットのツリー構造の取得にはどうしたら良いのか？

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
3	1	>>1 バーベキューしたい！
4	3	>>3 釣りもやりたい！
5	3	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

上記の階層構造から「id.1」の直近の子要素を取得するにはどうしたら良いのか？
以下のような処理によってスレッドの階層構造を持ったデータ取得することが可能。

SELECT
    c1.*,
    c2.*
FROM
    comments c1
LEFT OUTER JOIN comments c2
    ON c1.id = c2.parent_id
WHERE
    c1.id = 1;

一階層下の子要素まで取得できました。
では「id.1」に返信している「id.3」に対してさらに返信している二階層下のデータまで取得するには？

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
3	1	>>1 バーベキューしたい！
4	3	>>3 釣りもやりたい！
5	3	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

SELECT
    c1.*,
    c2.*,
    c3.*
FROM
    comments c1
LEFT OUTER JOIN comments c2
    ON c1.id = c2.parent_id
LEFT OUTER JOIN comments c3
    ON c2.id = c3.parent_id
WHERE
    c1.id = 1;

結合を増やすことでさらに下の階層まで取得できた。
階層がn個の不特定多数の場合は再帰クエリが使用できない場合かなり面倒。

データの削除

２つ目のデメリットのデータの削除をするにはにはどうしたら良いのか？

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
3	1	>>1 バーベキューしたい！
4	3	>>3 釣りもやりたい！
5	3	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

上記のツリー構造で「id.3」の投稿を削除したい場合、以下のような方法で削除する必要がある。

「id.3」のデータはツリーの非葉ノードとなっており、子が複数存在する。
そのまま該当の「id.3」のデータを削除してしまうと以下のデータは参照する「parent_id」が存在せデータの整合性が取れなくなる。

id	parent_id	comment
4	3	>>3 釣りもやりたい！
5	3	>>3 バーベキューの道具揃ってるよ！

「id.3」のデータを削除するには削除したいデータを含むツリーを辿っていき、葉ノードから「parent_id」を更新。

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
3	1	>>1 バーベキューしたい！
4	3⇨1	>>3 釣りもやりたい！
5	3⇨1	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

そして「id.3」と親子関係のデータがなくなったら削除。

id	parent_id	comment
1	null	夏休み海に行きたい
2	1	>>1 いいね！
4	1	>>3 釣りもやりたい！
5	1	>>3 バーベキューの道具揃ってるよ！
6	1	>>1 すまん、パス.....

しかし、論理削除をするカラムがあれば上記のような面倒な方法を使わずとも親子関係の整合性を保ちつつ簡単にデータの削除ができるため使うのであればこちらの方が現実的だろう。

|id|parent_id|comment|delete_flg|
|:---|:---|:--|:--|0|
|1|null|夏休み海に行きたい|0|
|2|1|>>1 いいね！|0|
|3|1|>>1 バーベキューしたい！|1|
|4|1|>>3 釣りもやりたい！|0|
|5|1|>>3 バーベキューの道具揃ってるよ！|0|
|6|1|>>1 すまん、パス.....|0|

アンチパターンを使用する場合

上記で挙げたデメリットを回避できる場合に関しては使用しても良いと考えている。

• 階層の深さが確定している場合
• 使用しているDBが再帰クエリを使用できる
• データの削除時、論理削除ができるカラムがあり整合性を担保できる
• そもそも親子関係が分かれば良いだけでツリー構造を維持しての取得は不要

代替ツリーモデル

1.経路列挙モデル

id	path	comment
1	null	夏休み海に行きたい
2	1/2	>>1 いいね！
3	1/3	>>1 バーベキューしたい！
4	1/3/4	>>3 釣りもやりたい！
5	1/3/5	>>3 バーベキューの道具揃ってるよ！
6	1/3/5/6	>>5 僕も持ってますよ！

簡単な説明

親子関係をそれぞれのノードにパスとして持たせるモデル。

メリット

• パターンマッチを用いてワンクエリでデータが取得できる

デメリット

• ジェイウォーク
• データの更新や削除時に隣接リストモデルよりも多くのクエリが必要

2.入れ子集合モデル

id	left	right	comment
1	1	12	夏休み海に行きたい
2	2	3	>>1 いいね！
3	4	9	>>1 バーベキューしたい！
4	5	6	>>3 釣りもやりたい！
5	7	8	>>3 バーベキューの道具揃ってるよ！
6	10	11	>>1 すまん、パス.....

簡単な説明

「left」より大きく「right」より小さいものが子孫。
「left」より小さく「right」より大きいものが先祖。
「left」「right」の付け方は再び雑な図だがこんな感じ....

メリット

• 子孫、先祖の一括取得がワンクエリで可能

デメリット

• データの更新、削除時に「left」「right」の再計算が必要
• 直近の親子関係の取得が面倒
• データの持ち方が複雑

3.閉包テーブルモデル

id	comment
1	夏休み海に行きたい
2	>>1 いいね！
3	>>1 バーベキューしたい！
4	>>3 釣りもやりたい！
5	>>3 バーベキューの道具揃ってるよ！
6	>>1 すまん、パス.....

ancestor	descendant
1	1
1	2
1	3
1	4
1	5
1	6
2	2
2	4
2	5
3	3
4	4
5	5
6	6

簡単な説明

別テーブルにてノード同士の関係性を定義するためのテーブルを追加して管理するモデル。
直近の親子関係のみではなく離れたノードの親子関係と自身を参照するパスも含める。

メリット

• ツリーの取得が容易
• データの追加、削除、更新が容易
• 整合性を維持しやすい

デメリット

• データ量がものすごく増える

まとめ

再帰クエリが使用できる環境であればアンチパターンを用いても良い。

しかし、使用できない場合は他のモデルの使用も検討する必要が出てくる。
それぞれのメリット、デメリット、使用環境と相談。

次回

ID Required

参考文献

SQLアンチパターン