クロージャーテーブルによる血縁関係の計算

家族の関係を調べるクエリは、見た目以上に難しいものです。「この2人に血縁関係はあるか？」「2人の間を何本の辺で結べるか？」「最も近い共通祖先は誰か？」人には自然な問いですが、各行に直接の親子関係だけを記録する標準的な隣接リストでは、答えを求める処理にコストがかかります。ツリーを再帰的にたどる必要があり、SQLでは再帰CTEを使います。正しい結果は得られますが、深いツリーでは遅く、複数の処理を組み合わせることも難しくなります。

クロージャーテーブルは、ツリー内のすべての到達可能な関係を事前に計算して保存することで、この問題を解決します。書き込み時に、すべての祖先・子孫の組を深さとともに明示的に記録します。書き込み処理は複雑になりますが、読み取りは大幅に高速化します。読み取りが書き込みよりはるかに多い家系図アプリケーションでは、ほぼ常に適切なトレードオフです。

隣接リストの問題

リレーショナルデータベースでツリーを保存する標準的な方法は隣接リストです。各行にidとparent_idを持つテーブルで、構造がわかりやすく、書き込みも簡単です。新しい人物を追加するには1行を挿入し、親との関係を変更するには1回更新するだけです。

ただし、「人物Xの祖先をすべて求める」には、ツリーを再帰的にさかのぼる必要があります。PostgreSQLや多くの現代的なSQLデータベースでは、再帰CTEで次のように記述します：

WITH RECURSIVE ancestors AS (
  SELECT id, parent_id, 0 AS depth
  FROM people
  WHERE id = :person_id

  UNION ALL

  SELECT p.id, p.parent_id, a.depth + 1
  FROM people p
  JOIN ancestors a ON p.id = a.parent_id
)
SELECT * FROM ancestors;

この方法で結果は得られます。しかし、深いツリーでは再帰CTEが各階層で行を走査するため、深さに応じてコストが増えます。3〜4世代の浅いツリーなら十分高速ですが、数百のノードを含む10〜15世代のツリーでは、性能の低下が目立ちます。さらに「XとYの共通祖先を求める」ようなクエリでは、2つの再帰CTEを実行して結果を結合する必要があり、コストが一層増えます。

クロージャーテーブルの構造

クロージャーテーブルは、人物を記録する主テーブルにもう1つのテーブルを追加する方式です。各行には、到達可能な関係として(ancestor_id, descendant_id)の組と、深さ（2人の間にある辺の数）を記録します。各人物自身も、深さ0の祖先として記録します。この記事の例は厳密なツリーを前提としています。各人物に登録されている親は最大1人で、祖先と子孫の各組には経路も深さも1つだけ存在します。1人に2人の親がいる実際の家系図や、複数の系統を通じて同じ祖先にたどり着く家系図では、スキーマの拡張（たとえば、経路ごとに1行を記録する、または各組の最小の深さを保持する）が必要です。その場合、LCAクエリが返すのは、祖先の夫婦の一方など、複数存在し得る最も近い共通祖先のうちの1人です。

CREATE TABLE family_closure (
  ancestor_id   INTEGER NOT NULL REFERENCES people(id),
  descendant_id INTEGER NOT NULL REFERENCES people(id),
  depth         INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX idx_closure_descendant ON family_closure (descendant_id);
CREATE INDEX idx_closure_ancestor   ON family_closure (ancestor_id);

人物Xに親が登録されていない場合、(X, X, 0)の1行を挿入します。人物Pの子としてXを追加する場合は、Pのすべての祖先も含めて挿入します：

-- Self-reference
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
VALUES (:x_id, :x_id, 0);

-- All ancestors of parent P become ancestors of X, at depth + 1
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
SELECT ancestor_id, :x_id, depth + 1
FROM family_closure
WHERE descendant_id = :parent_id;

つまり、世代の深さがNの人物を挿入するには、クロージャーテーブルにN+1行を追加します。深さが15〜20世代を超えることの少ない一般的な家系図では、十分に管理可能な量です。書き込みの追加負荷はツリー全体の規模ではなく、深さに比例します。

すべての祖先を取得する

クロージャーテーブルがあれば、ある人物のすべての祖先は、再帰処理を使わず1回の結合で取得できます：

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.ancestor_id
WHERE fc.descendant_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

このクエリは、descendant_idに対する1回のインデックススキャンで実行できます。コストはツリーの深さではなく、祖先の数に比例します。一般的な家系図の深さでは、通常は同等の再帰CTEより大幅に高速になり、ツリーが深くなるほど差が広がります。

対称となるクエリ、つまりある人物のすべての子孫を求める場合も、ancestor_idのインデックスを使う同じパターンです：

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.descendant_id
WHERE fc.ancestor_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

最小共通祖先

2人の最小共通祖先（Lowest Common Ancestor、LCA）は、2人が共有する最も近い祖先です。家系図では「この2人にとって最も近い共通祖先は誰か？」という問いの答えに相当し、関係に応じて祖父母、曾祖父母、あるいはさらに前の世代になります。

クロージャーテーブルでは、2人それぞれの祖先集合を結合し、共通する祖先に絞り込み、深さで並べ替えて最も近い祖先を求めます：

SELECT a.ancestor_id, a.depth + b.depth AS total_distance
FROM family_closure a
JOIN family_closure b ON a.ancestor_id = b.ancestor_id
WHERE a.descendant_id = :person_a
  AND b.descendant_id = :person_b
ORDER BY total_distance ASC
LIMIT 1;

このクエリは、2人からの距離の合計が最小となる共通祖先を返します。descendant_idに対する2回のインデックススキャンにより、ある程度大きなツリーでもミリ秒単位で実行できます。再帰処理もツリーを繰り返したどる処理もなく、インデックスが提供するもの以外に祖先集合を中間結果として実体化する必要もありません。

一方の人物が他方の祖先である場合も、このクエリで自然に処理できます。人物Aが人物Bの直系祖先なら、LCAはA自身です。Aは自分自身の祖先集合に深さ0で含まれるため、正しく返されます。

2人の間の距離

2人の間の距離は、共通祖先を経由して一方から他方へ到達するためにたどる親子関係の辺の数です。2人の深さの差ではなく、それぞれからLCAまでの距離の合計です。

SELECT MIN(a.depth + b.depth) AS degrees_of_separation
FROM family_closure a
JOIN family_closure b ON a.ancestor_id = b.ancestor_id
WHERE a.descendant_id = :person_a
  AND b.descendant_id = :person_b;

結合はLCAのクエリと同じですが、ORDER BY ... LIMIT 1の代わりにMIN()で集計します。いとこ同士の距離は4です。両者とも共通の祖父母まで2段階離れています。いとことその子の距離は5です。このクエリは、アプリケーション層でツリーをたどるロジックなしに、これらの値を正しく返します。

「いとこの孫」「大おじ」といった関係名を求めるには、深さの値を関係名に対応付ける追加のロジックが必要です。人物AからLCAまでの深さと人物BからLCAまでの深さを受け取り、関係名を返す関数で、一般的なケースの多くを扱えます。これはSQLではなくアプリケーション層の処理ですが、クエリから深さを明確な整数として取得できれば、実装は大幅に簡単になります。

更新時のクロージャーテーブルのメンテナンス

挿入は先に示したとおり単純です。削除や親子関係の変更には、より慎重な処理が必要です。

ツリーから人物を削除するには、その人物が祖先または子孫として現れるクロージャーテーブルのすべての行を削除します。その人物に子孫がいる場合、それだけでは不十分です。その人物の祖先と子孫を結ぶ行も削除する必要があります。そうしなければ、クロージャーテーブル上では両者の関係が残ります。それらの行を削除して初めて、子孫はその人物の祖先集合から切り離されます。これが適切な動作かどうかはアプリケーションによります。家系図では通常、子孫が登録されている人物の削除をアプリケーション層で防ぎます。

登録された親を別の人物に訂正するなど、親子関係を変更する場合は、子を根とする部分木の古いクロージャー行を削除し、新しい親に基づいて再挿入する必要があります。最も単純な実装は、影響を受ける部分木全体のクロージャー行をトランザクション内で削除し、新しい親からたどって再挿入する方法です。正しい結果が得られますが、トランザクション中は関連する行がロックされます。書き込みの少ない家系図アプリケーションの多くでは、許容できる制約です。

パフォーマンス比較

クロージャーテーブルと再帰CTEの性能差は大きく、ツリーの規模とともに広がります。500ノード、平均深さ12世代の人工的なツリーでは、再帰CTEによるLCAクエリはUIでわずかな遅さを感じる程度の時間がかかります。同じクエリをクロージャーテーブルの結合で実行すると十分高速で、遅延の主因はクエリ実行ではなくネットワークの往復時間になります。

クロージャーテーブルを維持するための追加の書き込み処理には、ツリーの深さに比例する、測定可能な挿入コストがかかります。ただし家系図では、読み取りに比べて挿入はまれです。人物を1人追加するごとに、関係や可視化を表示するために家系図へ数千回のクエリが実行されることもあります。このトレードオフはクロージャーテーブルに大きく有利です。

ストレージの追加使用量にも触れておきます。500人、平均深さ12のツリーでは、クロージャーテーブルに約6,500行（自分自身への参照を含め、1人あたり約13行）を保存します。PostgreSQLの行ごとのオーバーヘッド（23バイトのタプルヘッダーと行ポインター）と3つのインデックスを考慮しても、1行あたりの容量はおよそ100バイトの規模で、合計でも1メガバイト未満です。数万人を含む非常に大きな家系図データベースでも、クロージャーテーブルは現代のデータベースサーバーのメモリに十分収まり、キャッシュされたインデックスを高速に検索できます。

ReactFlowによる家系図の可視化：このデータベース設計で効率的に取得できる関係データを利用する可視化層
ウィジェットの国旗：ロケール依存の国名よりISO国コードが優れている理由：プログラムからの検索に、表示文字列ではなく安定した数値やコードの識別子を使うという共通の原則