【SQLアンチパターン】ナイーブツリーと閉包テーブル
こんにちは、CryptoGamesの高橋です。
ブロックチェーンサービスを行っている会社です。
今回は「SQLアンチパターン」の第３章の「ナイーブツリー（素朴な木）」について、見ていきます。
では早速、見ていきましょう。
１ 今回扱うケース
下のようなスレッドが存在するとします。
いろんな人が書き込みを行っていますね。
枝分かれや、スレッドが下に伸びていったりしています。
例えば「１」のコメントに対して、２つのスレッドが立っている、といった具合です。
このような、ツリー状の階層をデータベースに格納するのはどうしたら良いでしょう。
２ 用語の整理
ここで、用語の整理です。
それぞれの一つ一つを「ノード」と呼びます。
上のように、先端を「リーフ（葉）ノード」と呼びます。
その中間の、ルートでもリーフでもないものが「非葉ノード」です。
３ アンチパターン 隣接リスト
３ー１ 隣接リストの概要
アンチパターンとして紹介されていたのが「隣接リスト」です。
下のように、「そのコメントの親は誰か」に着目する構成です。
例えば、上のように、「コメント３の親はコメント２」、「コメント２の親はコメント１」となります。
３ー２ 隣接リストの構成
テーブルの構成は下のようになります。
「親ID」を設定し、そのコメントの親がどれであるかを入力します。
３ー３ 先祖のノードの取得の概要
では、例えば、コメント７の先祖を取得するためにどうすれば良いでしょう。
ちなみに、図で見れば簡単です。
下のように、１、４、６が先祖になります。
３ー４ 先祖のノードの取得のデータベースでの実施
では、データベース上はどのように取得するでしょう。
下のように、コメントテーブルをさらに右にくっつけることで実現します。
例えば、７番目の親は６なので、右にコメントID６の行をくっつけています。
これによって、次のようにわかります。
・コメント７の親はコメント６
・そのコメント６の親はコメント４
３ー５ 隣接リストの問題点
でも、１つ繋げただけだと、全部の先祖はわかりませんね。
下のように、今回はテーブルを３個つなげることで、ようやく全ての先祖を辿ることができました。
でも、これだと、階層が深くなればなるほど、テーブルを繋げなければいけませんね。
これが、この隣接リストがアンチパターンと呼ばれる理由です。
４ 解決策① 経路列挙（Path Enumeration）
４ー１ 経路列挙の概要
では、この解決策の一つである、「経路列挙」を見てみましょう。
特徴は「隣接リスト」のような「親ID」ではなく、パスを格納しているという点です。
4ー２ 経路列挙の利点と欠点
確かにこれなら、どれだけ階層が深くなっても、テーブルをつなげることなく、先祖や子孫を抽出することができます。
ただ、これには下のような問題点も残っています。
上のように、入力ミスが発生するかもしれません。
このような入力ミスの検出が困難なのが欠点です。
５ 解決策② 閉包テーブル（Closure Table）
５ー１ 閉包テーブルの概要
これらの問題を解決するために、「閉包テーブル」を使います。
なお、今回は本書に紹介されていた「入れ子集合」の解説は割愛します。
これは「親ー子」の関係ではなく、「先祖ー子孫」の関係に着目したやり方です。
例えば上のように、「１」の子孫は「２、３、４、５、６、７」となります。
それを下のような専用のテーブルに格納します。
なお、テーブルの１行目のように、「１」の子孫として自身である「１」も含めます。
他にも、例えば、４の子孫は「５、６、７」ですね。（テーブルには子孫に「４」も含めます。）
このように、今まで「親ID」や「パス」として同じ列にあった経路関係の列を切り離しているのが特徴です。
では、実際にこのテーブルでいろいろな操作が可能かを見てみましょう。
５ー２ 先祖ノードの検索
例 ７の先祖を検索する
下のように、「子孫」が７の行を検索すれば、見つかります。
５ー３ 子孫ノードの検索
例 ４の子孫を検索する
下のように、「先祖」が４の行を検索すれば、見つかります。
５ー４ ノードの追加
下のように、ノードを追加するとしましょう。
この場合、その先祖の組み合わせを追加すれば良いですね。
５ー５ 非葉ノードの削除
下のように、６以降のコメントを削除するとしましょう。
このように、「子孫」が「６、７」のものを消せば良いですね。
５ー６ ノードの付け替え
下のように、６以降のコメントを３の下に付け替えるとしましょう。
この場合は、まず現在の関係を断ち切るために、子孫が「６、７」の行を消します。
その後、下のように、新しく先祖になる部分を追加すれば良いですね。
５ー７ 入力誤りのチェック
では、下のような、入力誤りを事前に防ぐことはできるでしょうか？
これは「経路列挙」では難しい問題でした。
ただ、今回は、コメントテーブルのコメントIDにないものは、そもそも入力できないようにすれば良いですね。
５ー８ 閉包テーブルの問題点は？
こんな便利な閉包テーブルに問題はあるのでしょうか？
本書に書かれている問題としては、階層が深くなると、その分行数が増えていくということでした。
６ 最後に
いかがでしたでしょうか。
本書では「隣接リスト」の解決策として３つが紹介されていました。（うち、一つはこの記事では割愛）
その中で、最後の「閉包テーブル」を下のように書いていました。
「最も用途が幅広く、また唯一、ノードが複数のツリーへ所属することができます。」
私も個人的には、「閉包テーブル」がしっくりきました。
本記事は以上です。
皆さんの理解の一助になれば幸いです。
サポートをしていただけたらすごく嬉しいです😄 いただけたサポートを励みに、これからもコツコツ頑張っていきます😊