SQL Serverの計算列を使ってツリー構造データを完全に制約付ける

ツリー構造をSQLで扱うための定石はいくつか知られています。

• 隣接リスト
  最も単純で、各行が親に当たる行を自己結合で参照します。構造は単純ですが、古いSQLでは子孫を一気に取得する方法がないのでSQLアンチパターンでは「ナイーブツリー」と命名して安易に使わないよう戒めていますね。
• 閉包テーブル
  親子関係だけを記録するのが隣接リストですが、これはすべての先祖-子孫関係を相関テーブルに格納します。子孫の一括操作が可能になりますが、閉包テーブルの行数がツリー深度の2乗に比例して膨れあがる問題があります。
• 入れ子集合
  各行が【左】【右】で表される範囲をもち、この範囲の包含関係で親子関係を表現します。構造は単純で各種一括操作も容易ですが、データ挿入のときに範囲振り直しが必要になることがあるのと、異常データを制約で阻止できない欠点があります。
• 経路列挙
  ファイルのフルパスを'/'区切りとか'\'区切りの文字列で表せるように、各行のツリー上の位置をフルパス文字列で表現します。表の生データの可読性がすごい。異常データ排除の困難さに加え、パス名最大長の存在が問題。

整合性の保証がほしい

一長一短ある4つの手法ですが、異常データを完全に排除できるのは最初の隣接リストだけです。閉包テーブルはたしかに外部キー制約により存在しない行を指してしまうことはないのですが、「A→B」「B→C」という先祖-子孫関係があるのに「A→C」という先祖-子孫関係は存在しない、という矛盾した状態をどうしても禁止できません。

では最初の隣接リストならまったく整合性は保証できるのか、というと一点だけ問題があります。循環参照の問題です。「A→B」「B→C」「C→A」のような循環参照がどうしても許されてしまい、これはちゃんと対策しないとサブツリー一括操作が無限ループで死ぬやつです。

ツリーでの「深さ」も行に持たせる

循環参照の禁止は制約じゃ無理だからトリガ書いてチェックするしかないよとセルコ先生もプログラマのためのSQLでおっしゃっているわけですが、ここでSQL Serverです。SQL Server独自の計算列を使うことで循環参照を禁止する制約が書けるんです。

考え方は、各行に「深さ」カラムを持たせること。

深さ3の行は深さ2の行しか親にできません。このルールならば循環参照はあり得ない。それをSQL Serverではどう記述するのか*1。

CREATE TABLE tree (
	id INTEGER NOT NULL PRIMARY KEY IDENTITY,
	level INTEGER NOT NULL,
	p_id INTEGER,
	c_level AS level + 1 PERSISTED, -- 計算列（型は、計算結果の型であるINTEGERとなる）
	CONSTRAINT id_level UNIQUE(id, c_level),
	CONSTRAINT only_root_has_0_level CHECK((level=0 AND p_id IS NULL) OR (level>0 AND p_id IS NOT NULL)),
	CONSTRAINT parenthood FOREIGN KEY(p_id, level) REFERENCES tree(id, c_level)
);

levelが深さ、c_levelは深さ+1、つまり子世代の深さを表します。深さlevel=2の行で、必ずc_level=3なのです。

子に当たる行はp_id(親ID), levelの2カラムで親を参照します。この自己結合で、深さ3の行は深さ2の行だけを親に持つことが保証できました。

操作

この完全制約隣接リストツリーは、一括操作、特にノードの位置を移動する操作が一大事業となります。子孫すべての行について一気にlevelを書き換えてやらなければなりません。

SQL Serverの場合、INSTEAD OFトリガを作ってUPDATE命令の動作をごっそり入れ替えたりしてこの操作を隠蔽したりしますが、その書き方についてはまた回をあらためて。

*1:CHECK( (level=0 AND p_id IS NULL) OR (level>0 AND p_id IS NOT NULL) )という長ったらしい条件式は、「level=0と親がないのが同値」を意味していて普通ならCHECK( (level=0)=(p_id IS NULL) )と書くところです。boolean型がないTransactSQLではこのように書かないといけません。