tva
← Insights

Tables de fermeture pour le calcul des relations

Les requêtes de relations familiales sont trompeusement difficiles. “Ces deux personnes sont-elles liées ?” “Quel est notre degré de séparation ?” “Qui est l'ancêtre commun le plus proche ?” Ces questions semblent naturelles pour une personne mais sont coûteuses à répondre avec un stockage en liste d'adjacence standard, où chaque ligne n'enregistre qu'une paire parent-enfant directe. Y répondre nécessite de traverser l'arbre de manière récursive, ce qui en SQL signifie des CTEs récursives — correctes, mais lentes sur des arbres profonds et difficiles à composer.

Les tables de fermeture résolvent cela en précalculant et stockant l'accessibilité complète de l'arbre. Chaque paire ancêtre-descendant est enregistrée explicitement, avec la profondeur, au moment de l'écriture. Le résultat est des lectures nettement plus rapides au coût d'écritures plus complexes. Pour une application d'arbre généalogique où les lectures sont bien plus fréquentes que les écritures, ce compromis est presque toujours correct.

Le problème de la liste d'adjacence

La façon standard de stocker un arbre dans une base de données relationnelle est une liste d'adjacence : une table où chaque ligne a un id et un parent_id. C'est simple à comprendre et simple à écrire. Insérer une nouvelle personne nécessite une ligne. Mettre à jour une relation parent nécessite une mise à jour.

Mais répondre à “qui sont tous les ancêtres de la personne X ?” nécessite de remonter l'arbre de manière récursive. Dans PostgreSQL et la plupart des bases de données SQL modernes, cela s'exprime avec une CTE récursive :

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;

Ça fonctionne. Mais sur un arbre profond, la CTE récursive scanne les lignes à chaque niveau et le coût croît avec la profondeur de l'arbre. Pour un arbre peu profond — trois ou quatre générations — c'est suffisamment rapide. Pour un arbre s'étendant sur dix ou quinze générations avec des centaines de nœuds, les performances se dégradent notablement. Pire, composer deux CTEs récursives pour une requête comme “trouver l'ancêtre commun de X et Y” nécessite d'exécuter les deux récursions puis de joindre les résultats, ce qui multiplie le coût.

La structure de la table de fermeture

Une table de fermeture ajoute une seconde table à côté de la table principale des personnes. Chaque ligne dans la table de fermeture représente une relation d'accessibilité : une paire de (ancestor_id, descendant_id), plus la profondeur (nombre d'arêtes entre eux). Chaque personne est aussi son propre ancêtre à la profondeur zéro.

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

Quand la personne X existe sans parent, une ligne est insérée : (X, X, 0). Quand la personne X est ajoutée comme enfant de la personne P, l'insertion s'étend pour inclure tous les ancêtres de P :

-- Auto-référence
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
VALUES (:x_id, :x_id, 0);

-- Tous les ancêtres du parent P deviennent ancêtres de X, à profondeur + 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;

Cela signifie qu'insérer une personne à la profondeur de génération N nécessite d'insérer N+1 lignes dans la table de fermeture. Pour un arbre généalogique typique, où la profondeur dépasse rarement 15 ou 20 générations, c'est entièrement gérable. La surcharge d'écriture est proportionnelle à la profondeur, pas à la taille totale de l'arbre.

Requêter tous les ancêtres

Avec la table de fermeture en place, requêter tous les ancêtres d'une personne est une simple jointure sans récursion :

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;

Cette requête s'exécute avec un seul scan d'index sur descendant_id. Le coût est proportionnel au nombre d'ancêtres, pas à la profondeur de l'arbre. Pour un arbre de profondeur généalogique typique, c'est d'un ordre de grandeur plus rapide que la CTE récursive équivalente, et la différence croît à mesure que l'arbre s'approfondit.

La requête symétrique — tous les descendants d'une personne — suit le même pattern en utilisant l'index 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;

Ancêtre commun le plus bas

L'Ancêtre Commun le Plus Bas (LCA) de deux personnes est leur ancêtre partagé le plus récent. En termes d'arbre généalogique, c'est la réponse à “qui est l'ancêtre commun le plus récent de ces deux individus ?” — le grand-parent, ou l'arrière-grand-parent, ou plus loin selon la relation.

Avec une table de fermeture, la requête LCA est une jointure sur les deux ensembles d'ancêtres, filtrée sur les ancêtres partagés, ordonnée par profondeur pour trouver le plus proche :

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;

Cela retourne l'ancêtre partagé avec la plus petite distance combinée des deux personnes. Sur les deux scans d'index sur descendant_id, cela s'exécute en millisecondes même sur des arbres modérément grands. Il n'y a pas de récursion, pas de multiples passages dans l'arbre, et pas de matérialisation intermédiaire des ensembles d'ancêtres au-delà de ce que l'index fournit.

La requête gère aussi naturellement les cas où une personne est un ancêtre de l'autre. Si la personne A est un ancêtre direct de la personne B, le LCA est la personne A elle-même, et la requête la retourne correctement parce que A est dans son propre ensemble d'ancêtres à la profondeur 0.

Degré de séparation

Le degré de séparation entre deux personnes est le nombre d'arêtes familiales à traverser pour aller de l'une à l'autre via leur ancêtre partagé. Ce n'est pas la même chose que la différence de profondeur entre elles — c'est la somme des distances de chaque personne à leur 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;

C'est la même jointure que la requête LCA avec l'agrégat MIN() au lieu de ORDER BY ... LIMIT 1. Les cousins germains ont un degré de séparation de 4 (tous deux sont à deux étapes d'un grand-parent commun). Les cousins germains au premier degré ont un degré de 5. Cette requête retourne ces valeurs correctement sans aucune logique de traversal au niveau applicatif.

La description de la relation — “cousin au deuxième degré”, “grand-oncle” — nécessite une logique supplémentaire qui mappe les valeurs de profondeur sur des étiquettes de relation. Une fonction qui prend la profondeur de la personne A au LCA et la profondeur de la personne B au LCA et retourne une étiquette de relation couvre la plupart des cas courants. C'est de la logique applicative, pas du SQL, et c'est considérablement plus simple quand les valeurs de profondeur sont disponibles comme des entiers propres depuis la requête.

Maintenir la table de fermeture lors des mises à jour

Les insertions sont simples, comme indiqué ci-dessus. Les suppressions et les changements de relation parent nécessitent plus de soin.

Supprimer une personne de l'arbre signifie retirer toutes les lignes dans la table de fermeture où elle apparaît comme ancêtre ou descendant. Si la personne a des descendants, ces descendants sont maintenant déconnectés de l'ensemble d'ancêtres de la personne. Si c'est le comportement correct dépend de l'application — dans un contexte généalogique, supprimer une personne qui a des descendants enregistrés est typiquement empêché au niveau applicatif.

Changer une relation parent — corriger un parent enregistré vers une personne différente — nécessite de supprimer les anciennes lignes de fermeture pour le sous-arbre enraciné à l'enfant et de les réinsérer par rapport au nouveau parent. L'implémentation la plus simple est une transaction qui supprime toutes les lignes de fermeture pour l'intégralité du sous-arbre affecté et les réinsère en traversant depuis le nouveau parent. C'est correct mais verrouille les lignes concernées pendant la transaction. Pour la plupart des applications généalogiques, qui sont légères en écriture, c'est acceptable.

Comparaison des performances

La différence de performance entre les tables de fermeture et les CTEs récursives est significative et croît avec la taille de l'arbre. Sur un arbre synthétique de 500 nœuds et 12 générations de profondeur en moyenne, une requête LCA utilisant des CTEs récursives s'exécute dans une plage qui la rend légèrement lente dans un contexte d'interface. La même requête utilisant la jointure de table de fermeture est suffisamment rapide pour que la latence soit dominée par le temps d'aller-retour réseau plutôt que par le temps d'exécution de la requête.

La surcharge d'écriture de maintien de la table de fermeture ajoute un coût mesurable par insertion, proportionnel à la profondeur de l'arbre. Mais dans un contexte d'arbre généalogique, les insertions sont rares par rapport aux lectures — un arbre généalogique pourrait être interrogé des milliers de fois pour afficher des relations et des visualisations pour chaque personne ajoutée. Le compromis favorise fortement l'approche de table de fermeture.

La surcharge de stockage vaut aussi la peine d'être notée. Une table de fermeture pour un arbre de 500 personnes avec une profondeur moyenne de 12 stocke environ 3 000 à 5 000 lignes. À quelques octets par ligne, c'est négligeable. Même une très grande base de données généalogique avec des dizaines de milliers d'individus produit une table de fermeture qui tient confortablement en mémoire sur un serveur de base de données moderne, où elle sera mise en cache et disponible pour des lookups d'index rapides.

Ressources connexes

Articles connexes

Réduire les taux de retour Amazon FBA grâce à l'analyse systématique des données

Corriger le SEO après une migration de WordPress vers Astro : chaînes de redirections, sitemaps et nettoyage GSC

n8n vs Zapier : le bilan honnête d'un développeur