Verwandtschaft mit Closure Tables berechnen

Abfragen zu Verwandtschaftsbeziehungen sind schwieriger, als sie zunächst erscheinen. „Sind diese beiden Personen verwandt?“ „Wie viele Verwandtschaftsschritte liegen zwischen uns?“ „Wer ist der nächste gemeinsame Vorfahre?“ Für Menschen sind diese Fragen selbstverständlich. Mit einer üblichen Adjazenzliste, in der jede Zeile nur ein direktes Eltern-Kind-Paar erfasst, sind sie jedoch aufwendig zu beantworten. Dafür muss der Baum rekursiv durchlaufen werden, in SQL also mit rekursiven CTEs – korrekt, aber bei tiefen Bäumen langsam und schwer mit anderen Abfragen zu kombinieren.

Closure Tables lösen dieses Problem, indem sie vorab berechnen und speichern, welche Knoten im Baum voneinander aus erreichbar sind. Jedes Vorfahren-Nachfahren-Paar wird beim Schreiben ausdrücklich mit seiner Tiefe erfasst. Dadurch werden Lesezugriffe erheblich schneller, während Schreibzugriffe komplexer werden. Für eine Stammbaumanwendung, in der deutlich häufiger gelesen als geschrieben wird, ist dieser Kompromiss fast immer sinnvoll.

---

Das Problem mit Adjazenzlisten

Die übliche Methode, einen Baum in einer relationalen Datenbank zu speichern, ist eine Adjazenzliste: eine Tabelle, in der jede Zeile eine id und eine parent_id enthält. Das Modell ist leicht zu verstehen, und Schreibzugriffe sind einfach. Für eine neue Person wird eine Zeile eingefügt. Um eine Elternbeziehung zu ändern, genügt eine Aktualisierung.

Die Frage „Wer sind alle Vorfahren von Person X?“ erfordert jedoch, den Baum rekursiv nach oben zu durchlaufen. In PostgreSQL und den meisten modernen SQL-Datenbanken wird dies mit einem rekursiven CTE ausgedrückt:

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;

Das funktioniert. Bei einem tiefen Baum durchsucht der rekursive CTE jedoch auf jeder Ebene Zeilen, und der Aufwand wächst mit der Baumtiefe. Bei einem flachen Baum mit drei oder vier Generationen ist das schnell genug. Bei einem Baum mit zehn oder fünfzehn Generationen und Hunderten von Knoten lässt die Leistung spürbar nach. Noch aufwendiger wird es, zwei rekursive CTEs für eine Abfrage wie „Finde den gemeinsamen Vorfahren von X und Y“ zu kombinieren: Beide Rekursionen müssen ausgeführt und ihre Ergebnisse anschließend per Join verknüpft werden.

Die Closure-Table-Struktur

Eine Closure Table ergänzt die primäre Personentabelle um eine zweite Tabelle. Jede Zeile darin bildet eine Erreichbarkeitsbeziehung ab: ein Paar (ancestor_id, descendant_id) sowie die Tiefe, also die Anzahl der Kanten zwischen beiden Personen. Jede Person ist außerdem ihr eigener Vorfahre mit der Tiefe null. Die Beispiele in diesem Beitrag setzen einen strikten Baum voraus: Für jede Person ist höchstens ein Elternteil erfasst, sodass es für jedes Vorfahren-Nachfahren-Paar genau einen Pfad und eine Tiefe gibt. Reale Genealogien mit zwei Elternteilen pro Person oder mit Vorfahren, die über mehrere Linien erreichbar sind, benötigen ein erweitertes Schema (zum Beispiel eine Zeile pro Pfad oder die Speicherung der minimalen Tiefe pro Paar). Die LCA-Abfrage liefert dann einen von möglicherweise mehreren nächsten gemeinsamen Vorfahren, etwa eine Person eines Vorfahrenpaares.

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

Existiert Person X ohne Elternknoten, wird eine Zeile eingefügt: (X, X, 0). Wird Person X als Kind von Person P hinzugefügt, umfasst das Einfügen auch alle Vorfahren von 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;

Das bedeutet: Wird eine Person auf Generationstiefe N eingefügt, müssen N+1 Zeilen in die Closure Table eingefügt werden. Bei einem typischen Stammbaum, dessen Tiefe selten 15 oder 20 Generationen überschreitet, ist das gut handhabbar. Der zusätzliche Schreibaufwand ist proportional zur Tiefe, nicht zur Gesamtgröße des Baums.

Alle Vorfahren abfragen

Mit der Closure Table lassen sich alle Vorfahren einer Person mit einem einzigen Join ohne Rekursion abfragen:

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;

Diese Abfrage kann mit einem einzigen Index-Scan auf descendant_id ausgeführt werden. Der Aufwand ist proportional zur Anzahl der Vorfahren, nicht zur Baumtiefe. Bei einem Baum mit typischer genealogischer Tiefe ist das in der Regel deutlich schneller als der entsprechende rekursive CTE. Mit zunehmender Tiefe wächst der Unterschied.

Die umgekehrte Abfrage nach allen Nachfahren einer Person folgt demselben Muster und verwendet den Index auf 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;

Jüngster gemeinsamer Vorfahre

Der nächste gemeinsame Vorfahre zweier Personen, der Lowest Common Ancestor (LCA), ist ihr jüngster gemeinsamer Vorfahre. In einem Stammbaum beantwortet er die Frage „Wer ist der jüngste gemeinsame Vorfahre dieser beiden Personen?“ – je nach Beziehung ein Großelternteil, ein Urgroßelternteil oder ein weiter zurückliegender Vorfahre.

Mit einer Closure Table verknüpft die LCA-Abfrage die beiden Vorfahrenmengen, beschränkt das Ergebnis auf gemeinsame Vorfahren und sortiert nach der Tiefe, um den nächsten zu finden:

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;

Die Abfrage liefert den gemeinsamen Vorfahren mit der kleinsten Summe der Abstände zu beiden Personen. Mit den beiden Index-Scans auf descendant_id läuft sie selbst bei mittelgroßen Bäumen in Millisekunden. Es gibt keine Rekursion, keine mehrfachen Baumdurchläufe und keine zwischenzeitliche Materialisierung von Vorfahrenmengen über die vom Index bereitgestellten Daten hinaus.

Die Abfrage berücksichtigt auch Fälle, in denen eine Person Vorfahre der anderen ist. Ist Person A ein direkter Vorfahre von Person B, ist A selbst der LCA. Die Abfrage liefert dieses Ergebnis korrekt, weil A mit der Tiefe 0 zu ihrer eigenen Vorfahrenmenge gehört.

Abstand zwischen zwei Personen

Der Abstand zwischen zwei Personen ist die Anzahl der Verwandtschaftskanten, die über den gemeinsamen Vorfahren von einer Person zur anderen durchlaufen werden müssen. Er entspricht nicht der Differenz ihrer Tiefen, sondern der Summe der Abstände beider Personen zu ihrem 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;

Das ist derselbe Join wie in der LCA-Abfrage, jedoch mit der Aggregatfunktion MIN() anstelle von ORDER BY ... LIMIT 1. Cousins und Cousinen ersten Grades haben einen Abstand von 4, da beide zwei Schritte von einem gemeinsamen Großelternteil entfernt sind. Bei deren Kindern und dem jeweiligen Cousin oder der jeweiligen Cousine beträgt der Abstand 5. Die Abfrage liefert diese Werte korrekt, ohne dass die Anwendung den Baum selbst durchlaufen muss.

Die Bezeichnung der Beziehung – etwa „Cousin ersten Grades mit zwei Generationen Unterschied“ oder „Großonkel“ – erfordert zusätzliche Logik, die Tiefenwerte in Verwandtschaftsbezeichnungen übersetzt. Eine Funktion, die die Tiefe von Person A zum LCA und von Person B zum LCA entgegennimmt und eine Bezeichnung zurückgibt, deckt die meisten üblichen Fälle ab. Diese Logik gehört in die Anwendungsschicht, nicht in SQL. Sie wird deutlich einfacher, wenn die Abfrage die Tiefenwerte als eindeutige ganze Zahlen liefert.

Die Closure Table bei Änderungen pflegen

Wie oben gezeigt, sind Einfügungen unkompliziert. Löschungen und Änderungen an Elternbeziehungen erfordern mehr Sorgfalt.

Beim Löschen einer Person aus dem Baum werden alle Zeilen aus der Closure Table entfernt, in denen sie als Vorfahre oder Nachfahre vorkommt. Hat die Person Nachfahren, reicht das allein nicht aus: Auch die Zeilen, die ihre Vorfahren mit diesen Nachfahren verbinden, müssen entfernt werden. Andernfalls weist die Closure Table sie weiterhin als verwandt aus. Erst wenn diese Zeilen entfernt sind, sind die Nachfahren von der Vorfahrenmenge der gelöschten Person getrennt. Ob dieses Verhalten korrekt ist, hängt von der Anwendung ab. In genealogischen Anwendungen wird das Löschen einer Person mit erfassten Nachfahren üblicherweise in der Anwendungsschicht verhindert.

Wird eine Elternbeziehung geändert, also ein erfasster Elternteil durch eine andere Person ersetzt, müssen die alten Closure-Zeilen für den beim Kind beginnenden Teilbaum entfernt und relativ zum neuen Elternteil erneut eingefügt werden. Die einfachste Implementierung ist eine Transaktion, die alle Closure-Zeilen für den gesamten betroffenen Teilbaum löscht und sie ausgehend vom neuen Elternteil wieder aufbaut. Das ist korrekt, sperrt aber während der Transaktion die betreffenden Zeilen. Für die meisten genealogischen Anwendungen mit wenigen Schreibzugriffen ist das akzeptabel.

Performance-Vergleich

Der Leistungsunterschied zwischen Closure Tables und rekursiven CTEs ist erheblich und wächst mit der Baumgröße. Bei einem synthetischen Baum mit 500 Knoten und einer durchschnittlichen Tiefe von 12 Generationen dauert eine LCA-Abfrage mit rekursiven CTEs so lange, dass sie in einer Benutzeroberfläche etwas träge wirkt. Dieselbe Abfrage mit einem Closure-Table-Join ist so schnell, dass die Latenz hauptsächlich durch die Netzwerklaufzeit und nicht durch die Abfrageausführung bestimmt wird.

Die Pflege der Closure Table verursacht bei jeder Einfügung messbaren zusätzlichen Schreibaufwand, der proportional zur Baumtiefe ist. Bei Stammbäumen sind Einfügungen jedoch im Verhältnis zu Lesezugriffen selten: Für jede hinzugefügte Person kann der Stammbaum Tausende Male abgefragt werden, um Beziehungen und Visualisierungen anzuzeigen. Dieser Kompromiss spricht deutlich für Closure Tables.

Auch der zusätzliche Speicherbedarf ist zu berücksichtigen. Eine Closure Table für einen Stammbaum mit 500 Personen und einer durchschnittlichen Tiefe von 12 speichert ungefähr 6.500 Zeilen (etwa 13 pro Person, einschließlich des jeweiligen Selbstbezugs). Selbst unter Berücksichtigung des PostgreSQL-Overheads pro Zeile (ein 23 Byte großer Tupel-Header plus ein Zeilenzeiger) und der drei Indizes liegt der Speicherbedarf in der Größenordnung von hundert Bytes pro Zeile, insgesamt also unter einem Megabyte. Selbst eine sehr große genealogische Datenbank mit Zehntausenden von Personen erzeugt eine Closure Table, die problemlos in den Arbeitsspeicher eines modernen Datenbankservers passt. Dort kann sie zwischengespeichert werden und steht für schnelle Indexzugriffe zur Verfügung.

Weiterführende Beiträge

• ReactFlow zur Visualisierung von Stammbäumen – die Visualisierungsschicht, die die mit diesem Datenbankmuster effizient abfragbaren Verwandtschaftsdaten nutzt
• Flaggen in Widgets: Warum ISO-Ländercodes besser sind als sprachabhängige Namen – dasselbe Prinzip: stabile numerische oder codierte Kennungen statt Anzeigetexten für programmatische Abfragen verwenden