ソフトウェア開発の分野では、やってはいけない (やらない方がよい) 設計や実装の類型は「アンチパターン (anti-patterns)」として共有・認知されています。 個人的な観測の範囲でも、方々の現場で頻繁に目にするものとしては以下のようなものが挙げられるでしょうか:

魔法のボタン (英語版)

抽象化を行わず、インタフェースコードの中でロジックを実装してしまうこと

円-楕円問題 (英語版)

変更できない型から変更可能な派生型を作成する際の問題

定数インターフェイス (英語版)

インターフェイスを定数の定義に用いること

特殊事項によるコーディング (英語版)

特殊なケースが認識される度に、それに対応するコードを追加する

書き直しプログラミング（英語版）/偶然にもとづくプログラミング

コードを徐々に修正しながら動くかどうかを確認することで、問題を解決しようとする

アンチパターン - Wikipedia

Java で書かれたシステムにおいて、定義されているほぼすべてのクラスが "Constants" という (あるいは "SystemSettings" のような) 名前のインターフェイスを実装している、という「定数インターフェイス」などはもはや見慣れた風景。 「試験 (テスト) 工程の充実」をコンセプトとして掲げる開発現場の実態が、実は単なる「書き直しプログラミング」の連続でしかない、などといったケースも珍しいものではありません。

コード全体が非常に「雑」に書かれており、ブラックボックステストによってかろうじて動作が保証されているシステムというのは頻繁に眼にするところ。

内製のススメ

データベース設計についても、こうしたアンチパターンは存在しており、関係データベースにおける配列の表現 で取り上げたような「カラムの反復定義」や「カンマ区切り」で配列を表現する手法などがそれに該当します。 こうした「べからず集」はいずれも経験に裏打ちされた実効性のあるものなのですが、その中に「これはアンチパターンに含めるべきではないのでは?」と思わざるを得ないものがひとつ。 それが、このエントリのテーマである "Naive Tree (素朴な木)" です。

その名が示すように、"naive tree" とは木構造 を表現するためのテーブル設計手法のひとつ。 例えば、左図に示すような階層構造を表現できるようなテーブルを考えてみましょう。 (通常であれば主キー "id" は整数型にするところですが、今回は説明の簡易さのため文字列としています。 また、項目のピックアップがあまりにも雑かつ恣意的である点へのツッコミはご遠慮ください。)

CREATE TABLE "creature" (
    "id"     VARCHAR(32) PRIMARY KEY,
    "parent" VARCHAR(32),
    "name"   TEXT        NOT NULL,
    FOREIGN KEY ("parent") REFERENCES "creatures" ("id")
);

上記は本当に単純な──各ノードがただそれ自身の「直接の」親ノードを知っているという──構造。 実際に左図のデータを格納したテーブルの内容は以下のようになります:

関係データベースの考え方からすると他の表現方法を考えるのが難しいほど当たり前の構造ですが、どこに問題があるのでしょうか。 ちなみに、"naive" という単語には「素朴な」の他に、「間抜けな」「世間知らずの」といったネガティブなニュアンスがあります。

(特に若いために) 世間知らずの、単純な、純真な、だまされやすい、単純で、純真で、 (特定の分野に)未経験な、先入的知識のない、甘い、素朴な

naiveの意味・使い方 - 英和辞典 Weblio 辞書

"naive tree" がアンチパターンとされる理由は、それを語る人にもよりますが、殆どの場合ただひとつ、

という事実に集約されるようです。

ナイーブツリー選択のデメリット

• (サブ) ツリーを引っこ抜けない
  • ツリー全体
  • あるいはあるコメントのサブツリー
• n 階層取得したい場合は...?
  • 子が存在し続ける限り自動で join し続けてくれるSQLは書けない
    • 取得できる階層が固定される
  • 必然的にある任意の (サブ) ツリーのコメント総数みたいな集約関数も使えない
• 非葉ノードとそのサブツリーの削除
  • コメント1削除
  • コメント1を親に持つコメントを削除
  • ...とやりたいけど、参照整合性のために子から削除する必要がある
  • c1、c1 を親に持つ (c2)、c2 を親に持つ ... を結果が返らなくなるまで繰り返して削除対象のコメントを取得し、子側から delete しないとダメ
  • とは言え delete on cascade が使えればこれは自動化できる

SQLアンチパターン - ナイーブツリー (pp. 14, 15)

何故ダメなのか

階層の探査をするクエリが非効率的。 1階層下の子ノードの集合を取るのには、以下の様なクエリが必要。

SELECT d1.*, d2.*
FROM Departments d1
  LEFT OUTER JOIN Departments d2
    ON d2.parent_id = d1.department.id;

これがn階層になると、d1., d2., ... dn.* となり、もちろん階層分だけJOINすることになる。

中間のノードの削除を行う際に、親子関係を適切に組み替えるためのクエリも複雑になる。

SQLアンチパターンその2 ナイーブツリー (素朴な木) - blog.toxn

確かに、この点は見過ごせません。 前節の生物分類データの例でいうと、「動物」以下のすべてのノードを取得するためには JOIN による自己結合や、カーソルや呼び出し元の手続き型プログラムによる反復 (俗に「ぐるぐる系SQL」と呼ばれる) を用いる必要があり、パフォーマンスおよび保守・可読性の両面において大きな問題となります。

しかし、その程度の問題であれば既によく知られた解決策──前節で紹介した、naive tree の問題を指摘する記事の中でも「閉包テーブル (closure table) モデル」として言及されている手法──が存在しています。 元となる木構造を表すテーブルとは別に、その各ノードの包含関係を格納するテーブルを定義します。

CREATE TABLE "creature_path" (
  "child"        VARCHAR(32),
  "ancestor"     VARCHAR(32),
  "depth_offset" INTEGER NOT NULL,
  PRIMARY KEY ("ancestor", "child")
);

この包摂テーブルには、あるノード ("child") から見て「祖先 ("ancestor")」にあたるノードの情報を保持させるようにします。 少々長くなりますが、その内容を書き下すと以下の通り:

パフォーマンス向上のために事前に計算した結果を保存しておくことから、個人的にこの種のテーブルのことを「キャッシュ (cache)」と呼んでいるのですが、一般的な用語ではないようなので、他人に伝える際は使わない方がよいかもしれません。

さて、このテーブルの情報があれば、たとえば "すべての" 「植物」を選択するクエリは以下のように書くことができます:

外部キー (foreign key) 参照の整合性を保持するため若干の工夫が必要ではありますが、削除についても同様に実行が可能です。

この手法のデメリットとしては「閉包テーブルのデータが大きくなる」ことがあげられますが、例えばツリーが平衡ないしそれに近い状態にあれば、ノード数 n に対して閉包テーブルの列数のオーダはたかだか

であり、通常の用途ではまず問題になることはない範囲。 加えて、この閉包テーブル "creature_path" が保持するデータはすべてテーブル "creature" の内容から計算で求めることが可能であり、バックアップ等の目的でエクスポートを行う際にはこれを対象から除外することができる (インポートした先で再度計算すればよいため) ため、運用におけるデータ取扱量が劇的に増えることもないはずです。

となると、次のような疑問は出てこないでしょうか。

個人的には、その分類は甚だ不当であり、むしろ "naive tree" をアンチパターンとして避けるために、次節に示すような「真のアンチパターン」と呼ぶべきテーブル設計を採用してしまうことの弊害が大きいと考えています。

naive tree の短所、即ち先述の「あるノードと (その直接の親以外の) 祖先ノードとの関連が把握しづらい」という問題をどうすれば回避できるかと考えたとき、関係データベース (RDB) の特性を理解していない、あるいは、テーブルを増すことを厭う怠惰な設計者は「経路列挙モデル」という、各ノードにすべての祖先ノードのIDを持たせる手法を採用しがちです。

CREATE TABLE "creature" (
  "id"  VARCHAR(32) PRIMARY KEY,
  "path" TEXT NOT NULL,
  "name" TEXT NOT NULL
);

各ノードに "path" として、共通祖先 (root) からの経路を持たせてるのが特徴。 こうしたデータ構造であれば、先と同様に (すべての)「植物」を選択するクエリは次のように書くことができます。

閉包テーブルモデルのように結合 (JOIN) を行う必要がないため、こちらの方が簡潔に見えるかもしれません。 それに加えて、この経路列挙モデルは、コンソール等で見た際に「(人間にとって) 分かりやすい」といった理由から採用されることが多いのですが、実際にはこれこそが真にアンチパターンと呼ぶに相応しい、デメリットだらけの手法であることにお気づきでしょうか。

まずはテーブルに対して外部キー制約が掛けられていない (というか掛けられない) ことに注目して欲しいわけですが、さてここで生物学を多少でも学んだ人ならば指摘したくてウズウズしているだろう誤りを正すときがやってきました。 ご存知の通り、かつては植物の一種であると見なされていた菌類は、現代においては「菌界」という「動物界」「植物界」などと並ぶ独立した系統をもつものとされています。 この知識のアップデートに従って、右図のように「菌類 (fungus)」を「植物 (plant)」から外し、共通祖先 (root) の直下に移動させるには、どのようなクエリを発行すればよいでしょうか。

でOK? いいえ、これでは「シイタケ (shiitake)」が '/plant/fungus/shiitake' という不正なパスに取り残されてしまうのでNG。 しかもここには、そうした整合の取れていないデータであっても、制約がかけられていないためにデータベース (正確にはRDBMS) はエラーも警告も発することなく、この更新を受け入れてしまうという問題があります。 これではデータの整合性を保証することができないため、トラブルが発生した際により広い範囲を調査しなければならないという事態に陥るでしょう。

実際、この処理を一般的な状況下でSQL一本で行うには、後方参照ありの正規表現など、非標準的かつ複雑なクエリを生成する必要があります。 一方 "naive tree" であればこの更新に難しいことは何もありません。 (併せて閉包テーブルの更新を行う必要はありますが。)

さらに言うならば、経路情報を格納するカラム "path" は、データベース設計におけるより明確なアンチパターンである「ジェイウォーク (信号無視)」あるいは「"スマート" カラム」に該当します。

ジェイウォーク is 単一列に複数の値を格納するSQLアンチパターン

ジェイウォーク選択のデメリット

• 参照が死ぬ
• 更新が死ぬ
• 妥当性検査、参照整合性が死ぬ
• 仕様変更で死ぬ

SQLアンチパターン - ジェイウォーク (pp. 2, 19)

2.4 データベースの不吉な臭い

Fowler (1997) は「コードの不吉な臭い」という概念を持ち込んだ。 それはリファクタリングの必要性を感じされる, コードによく見られる問題のことである。 一般的なコードの臭いには, スイッチ文, 長すぎるメソッド, 重複したコード, 属性/操作の横恋慕などがある。 同じように, データベースにも, リファクタリングの必要性を感じさせる不吉な臭いがある (Ambler 2003)。 例えば次のようなものである。

「スマート」カラム

スマートカラムとは, データ内の位置によって表す概念が異なるカラムのことである。 例えば, 顧客IDの最初の4桁が顧客の担当支店を表しているとすると, その顧客IDはスマートカラムということになる。 解析すると, より細かい情報 (担当支店IDなど) が得られるからである。 ( 中略 ) スマートカラムは, どこかの時点でそれを構成するデータフィールドに整理しなおし, データベースがそれぞれを独立した要素として簡単に扱えるようにする必要がある。

『データベース・リファクタリング』/ 著: スコット W. アンブラー, ピラモド・サダラージ

アンチパターンではない正当な手法 (naive tree) をアンチパターンと勘違いし、それを避けた結果として、より取り回しの悪い本物のアンチパターン (経路列挙モデル) を採用してしまうという判断ミスはできれば避けたいものです。

このエントリでは関係データベースにおける木構造の表現について説明してきましたが、実は一般的な業務システムにおいて木構造が必要になる場面はそれほど多くありません。 その理由としては、現実世界におけるモノゴトの分類はきれいな木構造に収まらないものが多いということが挙げられます。 物販系のシステムなどでは商品カテゴリが木構造として登録されることがありますが、例えば、

• 「書籍」(下位分類として「文庫」「雑誌」など)
• 「音楽」(下位分類として「CD」「楽器」など)

のような分類を設定したとして、「ヴァイオリンの弾き方指南書」はどちらに入れるべきでしょうか? もちろん、その本には ISBN が割り当てられているでしょうから「書籍」に入れるべきではありますが、「音楽」での検索結果にも出てきてほしいところ。 このような場合、階層構造を作らず、多対多で柔軟な関連付けができるタグ付け (tagging) を採用した方が、管理者・利用者双方にとって使い勝手の良いシステムになることが多いようです。

また、企業や自治体などの組織系統が木構造としてモデル化されることもありますが、そのような場合には大抵、ノード数は100未満、階層の深さはせいぜい 5 といったところに落ち着きます。 そのような小さなデータセットに対しては、テーブルの内容すべてを一気に読み込んでしまい、メモリ上で木構造を構築する方が面倒がなく取り回しも良くなります。

モデル化において重要なのは、どの情報が必要で、どの情報が不要かという見極め。 必要な情報が抜け落ちればシステムは用を為さず、不必要な情報が入り込めばプログラムの複雑さが増して保守が困難になります。 つまり、モデル化というのは、対象から必要な情報だけを抜き出す作業。 言い換えれば、モノゴトの「本質」を見抜くことに他なりません。

見る力