ナイーブツリー(素朴な木)

木構造を隣接リストで表現すると、n階層の検索をすることができなくなったり、ノード全体を削除するのが複雑になるという主張である。隣接リストとは、親への参照を作成するだけである。自分自身と親への参照を持っているに過ぎない設計なので、ある非葉ノードを削除する場合は、下層から削除しないと、参照整合性制約でエラーに成ってしまう。A-B-C-Dという構造があり、C以下を削除しようとした場合にCを先に削除するとDがもつCへの参照が切れてしまうという問題である。
一方、このアンチパターンを使用しても良い場合の一つとして、階層問い合わせが紹介されている。一部のDBMS再帰的なクエリを記述することができるためn階層の検索が(やや複雑ではあるが)可能になる。
さて、このパターンではとても気になる記述があった。

例えば、ノードの数(スレッドのコメント数)をCOUNTで数えたり、ノードの値(例:製造業の各部品のコスト)をSUMで合計する場合などにはすべての子孫を対象にする必要があります。(p 16)

このうち、前の方の記述は良い。メールのスレッドは木構造である。ただ、後ろは多くの場合は正しくない。製造業の各部品のコストということは、部品表を想定しているようだが、部品表は多くの場合は木構造ではない。DAG(非循環有向グラフまたは無閉路有向グラフ)である。違いは一つの部品の親は複数であるということだ。共通して使われる部品は多数ある。こういう場合は、木構造にはならない。そして、そうした場合は、殆どの場合、隣接リストによる表現が一般的な設計となる。先ほど話したように、リレーショナルモデルは配列を持てないので、一般的には「親部品コード・子部品コード」を主キーにした「部品表テーブル」という設計が一般的である。この設計ではA-B-C-Dの構造でC以下を削除する際に、B-C、C-Dの順番で消しても参照整合性制約の違反にはならない。
さて、次に解決策を1つずつ見ていく。

経路列挙

これは、先のジェイウォークのアンチパターンを使って一つ上の親だけでなく祖先全体をもつというやり方である。たとえばパスをスラッシュで区切る例を出している。例えば、コメントの階層を1/4/6/7というように表現し、このままの形で保存する。1/4の下を検索したい場合はLike '1/4/%'とすればよい*1
さて、アンチパターンを使わないようにするなら、テーブルはやはり分けるべきであろう。ただし、そうすると順序がわからなくなる。この時は木のレベル(深さ)をデータとして持てば良い。上記であればこのようなテーブルを別に作る。

レベル 祖先コメントID 子コメントID
0 1 7
1 4 7
2 6 7

とすると、1/4の下を検索するSQLは以下のとおりである。

select
 *
from
 コメントデータ
 inner join
 祖先コメントテーブル on
コメントデータ.コメントID = 祖先コメントテーブル.子コメントID
where
 祖先コメントテーブル.祖先コメントID = 4
;

ちなみにこの解決策は「閉包テーブル」という名前でこの本のおすすめの解決策の一つとして記述されている。なお、木構造なので、1/4の下は4の下と同じ意味である。DAGで、親が複数あったとしても親に応じて子が変わるわけではないので、同じパターンの検索で良い。
ただし、この本にもあるように、経路列挙は経路列挙値をソートすると階層全体を深さ優先探索の並び順で表示できるが、閉包テーブルは実現が難しい。閉包テーブルは自分の祖先や子供に何がいるかを検索するのには便利だが、階層構造全体を表現する際に一般的な深さ優先探索の並び順で検索することが簡単にはできない。

入れ子集合

1の子に2と3、3の子に4と5があるとする。このとき、親をX、子をYとZとした時にX(Y Z)と表現すると、下記のようになる。

1(2() 3(4() 5()))

この括弧の位置を保存する。例えば1であれば、1と10。2であれば、2と3となる。そうすると、子孫はこの位置の間に常にある。祖先は逆に自分の括弧の位置を含む値を取得すれば良い。ただし、直近の親をとるには、自身と親の間にノードがないことを検索する必要が有るため、複雑になる(外部結合して、NULLのものをとるというやりかた)。ただ、自分の祖先のうち、開始カッコが最も大きいものを取ればいいので、SQLだけで頑張らなければ比較的やさしい。一方で、括弧の位置を再構築するのにコストがかかるのが厳しい。ちなみに、再構築を減らすという入れ子区間モデルとは、実数を使って間に割り込ませるという素晴らしい方法である。
また、階層構造の深さ優先探索の検索も左側のカッコの順番で検索すれば簡単だ。

私の結論

この本に真っ向から対立するようだが、私は隣接リスト+階層問い合わせを最優先に考えるべきだと思う。素朴な構造であるがゆえに、更新処理に対する影響が最も出にくい。とにかく一番怖いのは、バグなどによりデータの整合性が壊れることである。それが最も起きにくい。ただし、先に述べたように親と子のペアのテーブルを別に作るという前提であり、この本の例のような1つのテーブルの中に親への参照だけをひとつ持っているという設計はかなりまずい。DAGにも応用できない。
木構造であれば、私は入れ子集合も検討すべきだと思う。この本では全くおすすめされていないが、実数を使うという入れ子区間モデルのアイデアはやはり素晴らしい。洗い替えが必要な点だけが問題だが、経路列挙の順番(深さ優先探索の順番)で簡単に検索もでき、ジェイウォークのアンチパターンにもはまらない。

*1:厳密にはLIKE '%/4/%'でもよい。ただし、前方一致ではないため、索引を設定しても使用されないという問題がある。索引は通常昇順で格納されているため、前方一致なら範囲検索ができる。