flint>flint blog>2018>Jun>24>Naive Tree はアンチパターンか

Naive Tree はアンチパターンか

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

魔法のボタン (英語版)
抽象化を行わず、インタフェースコードの中でロジックを実装してしまうこと
円-楕円問題 (英語版)
変更できない型から変更可能な派生型を作成する際の問題
定数インターフェイス (英語版)
インターフェイスを定数の定義に用いること
特殊事項によるコーディング (英語版)
特殊なケースが認識される度に、それに対応するコードを追加する
書き直しプログラミング(英語版)/偶然にもとづくプログラミング
コードを徐々に修正しながら動くかどうかを確認することで、問題を解決しようとする

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")
);

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

id parent name
animal NULL 動物
bracken magnoliophyta ワラビ
cat mammal ネコ
dog mammal イヌ
fungus plant 菌類
mackerel osteichthyes サバ
magnoliophyta plant 被子植物
maiberry magnoliophyta クワ
mammal animal 哺乳類
osteichthyes animal 硬骨魚類
plant NULL 植物
pteridophyte plant シダ類
reptilia animal 爬虫類
shiitake fungus シイタケ
snake reptilia ヘビ
tuna osteichthyes マグロ

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

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

何が問題か

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

あるノードと (その直接の親以外の) 祖先ノードとの関連がたどりづらい

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

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

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

何故ダメなのか

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

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

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

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

確かに、この点は見過ごせません。 前節の生物分類データの例でいうと、「動物」以下のすべてのノードを取得するためには 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")」にあたるノードの情報を保持させるようにします。 少々長くなりますが、その内容を書き下すと以下の通り:

child ancestor depth_offset
animal animal 0
bracken bracken 0
bracken plant 2
bracken pteridophyte 1
cat animal 2
cat cat 0
cat mammal 1
dog animal 2
dog dog 0
dog mammal 1
fungus fungus 0
fungus plant 1
mackerel animal 2
mackerel mackerel 0
mackerel osteichthyes 1
magnoliophyta magnoliophyta 0
magnoliophyta plant 1
malberry magnoliophyta 1
malberry malberry 0
malberry plant 2
mammal animal 1
mammal mammal 0
osteichthyes animal 1
osteichthyes osteichthyes 0
plant plant 0
pteridophyte plant 1
pteridophyte pteridophyte 0
reptilia animal 1
reptilia reptilia 0
shiitake fungus 1
shiitake plant 2
shiitake shiitake 0
snake animal 2
snake reptilia 1
snake snake 1
tuna animal 2
tuna osteichthyes 1
tuna tuna 0

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

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

SELECT "c".* FROM "creature" AS "c" JOIN "creature_path" AS "cp" ON "c"."id" = "cp"."ancestor" WHERE "cp"."ancestor" = 'plant';

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

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

( log n )2

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

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

指摘される欠点に対して「閉包テーブルモデル」という決定版とも呼べるような解決策をもつ naive tree をアンチパターンとして分類することは果たして妥当か。

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

真のアンチパターン

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

CREATE TABLE "creature" (
  "id"  VARCHAR(32) PRIMARY KEY,
  "path" TEXT NOT NULL,
  "name" TEXT NOT NULL
);
id path name
animal /animal 動物
bracken /plant/magnoliophyta/bracken ワラビ
cat /animal/mammal/cat ネコ
dog /animal/mammal/dog イヌ
fungus /plant/fungus 菌類
mackerel /animal/osteichthyes/mackerel サバ
magnoliophyta /plant/magnoliophyta 被子植物
maiberry /plant/magnoliophyta/maiberry クワ
mammal /animal/mammal 哺乳類
osteichthyes /animal/osteichthyes 硬骨魚類
plant /plant 植物
pteridophyte /plant/pteridophyte シダ類
reptilia /animal/reptilia 爬虫類
shiitake /plant/fungus/shiitake シイタケ
snake /animal/reptilia/snake ヘビ
tuna /animal/osteichthyes/tuna マグロ

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

SELECT * FROM "creature" WHERE "path" = '/plant' OR "path" LIKE '/plant/%';

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

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

UPDATE "creature" SET "path" = '/fungus' WHERE "id" = 'fungus'

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

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

UPDATE "creature" SET "parent" = NULL WHERE "id" = 'fungus'

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

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

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

  • 参照が死ぬ
  • 更新が死ぬ
  • 妥当性検査、参照整合性が死ぬ
  • 仕様変更で死ぬ
データベース・リファクタリング

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

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

「スマート」カラム
スマートカラムとは, データ内の位置によって表す概念が異なるカラムのことである。 例えば, 顧客IDの最初の4桁が顧客の担当支店を表しているとすると, その顧客IDはスマートカラムということになる。 解析すると, より細かい情報 (担当支店IDなど) が得られるからである。 ( 中略 ) スマートカラムは, どこかの時点でそれを構成するデータフィールドに整理しなおし, データベースがそれぞれを独立した要素として簡単に扱えるようにする必要がある。
『データベース・リファクタリング』/ 著: スコット W. アンブラー, ピラモド・サダラージ

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

身も蓋もない話

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

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

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

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

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

Narita (気になる木になる)
このエントリーをはてなブックマークに追加

Comments

データベース上で柴犬の情報は頻繁に使われるので特別扱いすべき ( Author: nsdt <lo46as67ETep9> )

プログラミングのセンスの良し悪しって、現実世界にあることがらのモデル化が上手にできるか、っていうことなのかな。

SEとPGの境界 ( Author: なりた )

> 現実世界にあることがらのモデル化が上手にできるか

それはどちらかというと「プログラミング (実装)」ではなく「設計」の手管ですね。プログラミングにおいては現実世界の事柄とは直接の関連を持たない概念を扱う能力も必要になります。例えば、「クイックソート」や「ハッシュ値」などは、「自然な発想」からの産物ではありえず、数学的な抽象化を経たからこそたどりつくことのできた概念だと言えるでしょう。

今回のエントリの例で言えば、木構造を naive tree なテーブルで表現するのが「設計」の、閉包テーブル (キャッシュ) でパフォーマンス向上を図るのは「プログラミング (実装)」の領分だと考えています。

まぁ実際は、どちらかを専門としつつ他方もある程度こなせる人間がいないと、システム開発って上手くいかないもんなんですけどね。

Untitled ( Author: noname <hOxU2S7B75wI> )

> 「閉包テーブルモデル」という決定版とも呼べるような解決策をもつ naive tree をアンチパターンとして分類することは果たして妥当か。

閉包テーブルモデルにした時点で naive tree ではないので、naive tree がアンチパターンであることに疑問の余地はないですよ。

経路列挙モデルが真のアンチパターンであることは仰るとおりだと思います。

Re: untitled ( Author: なりた )

noname さん:

> 閉包テーブルモデルにした時点で naive tree ではないので、naive tree がアンチパターンであることに疑問の余地はないですよ。

(1)
Naive tree はそれ単体で対象の完全な表現であり、閉包テーブルモデルの補助がなくても (効率は悪いにせよ) 用を為します。閉包テーブルモデルは naive tree を置き換えるものではなく、あくまで naive tree の「補助」として追加されるものに過ぎません。エントリ本文で「キャッシュ (cache)」と表現しているのはそうした意味合いです。そんなわけで、「閉包テーブルモデルを採用したとしても、naive tree は naive tree のままである」というのが私の見解です。

(2)
Naive Tree は祖先あるいは子孫ノードへのアクセス効率が悪い (または煩雑) という理由で「アンチパターン」に分類されています。しかし、RDBとしての正規性を保ち、かつ二分探索木 (binary-search tree) のようにキーの型に制約がないという点、そしてエントリ本文および前述 (1) で述べているようにアクセス効率の悪さを (モデル本体の構造を変えずに) 「補う」方法があるという時点で所謂「ベストプラクティス」であろうと考えています。「RDB で木構造を表現することそのものがアンチパターン」だと仰るならば、「そうですね」としか申し上げようがありませんが。

Untitled ( Author: noname <kloHjQs6BGIJ> )

閉包テーブルモデル もそれ単体で対象の完全な表現です。
この記事に載っているのは「naive tree」+「閉包テーブルモデル」のハイブリッドモデルだと思われます。

閉包テーブルモデルでは、元となる木構造を表すテーブルに親ノードの情報は必要有りません。

Untitled ( Author: Unknown <Z5irtxhtHL7K> )

素晴らしい解説記事、ありがとうございます。とても分かり易かったです。

一点質問がございます:
閉包テーブルで階層構造を表現しつつ、かつ順番を保持しなければいけない時、成田様でしたらどう設計しますか?

例えば「哺乳類」の前には必ず「爬虫類」を表示しなければいけない、といった順番をユーザが自由に設定できる状況です。

私は閉包テーブルに「order」カラムを追加する方法を考えていたのですが、ユーザが順番を変更した時のクエリが複雑なため、他に良い方法は無いものか考えておりました。

表示順の設定 (Re: Untitled) ( Author: なりた )

Unknown さん:

この記事の主題の通り、私は naive tree をアンチパターンであるとは考えていないので、表示順を表すカラムが必要になったとすれば、naive tree のテーブルに対してカラム order の追加を行います。この場合、表示順変更のクエリは自明です:

UPDATE "creature" SET "order" = ? WHERE "id" = ?;

それを前提とした上で、どうしても閉包テーブル上でこれを表現しなければならない事情があるとすれば、Unknown さんが仰っている通り、閉包テーブルにカラム order を設け、depth_offset = 0 (すなわち自分自身を表す) 列についてのみ有効とする、という方法を考えるでしょう。この order の値は、同一の ancestor 値を持ち、かつ depth_offset = 1 となる (すなわち同じ親の直下の子要素を表す) 列の集合における表示順ということになります。例えば「動物 (animal)」直下の要素を指定順に表示したい場合は、自己結合を用いた以下のようなクエリで選択を行います:

SELECT
 "c".*
FROM
 "creature_path" AS "c"
 JOIN
  "creature_path" AS "co"
 ON
  "co"."ancestor" = "c"."ancestor" AND
  "co"."depth_offset" = 0
WHERE
 "c"."ancestor" = 'animal' AND
 "c"."depth_offset" = 1
ORDER BY
 "co"."order"
 "c"."child";

指定順を変える場合は、すべての列ではなく、"depth_offset" = 0 (あるいは "child" = "parent") である列のみを更新します:

UPDATE "creature_path" SET "order" = ? WHERE "child" = ? AND "depth_offset" = 0;
Author
URI
Mail
Title
Content