tva
← Analyses

Tables de fermeture pour calculer les liens de parenté

Les requêtes sur les liens de parenté sont plus difficiles qu’il n’y paraît. « Ces deux personnes ont-elles un lien de parenté ? » « 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 à traiter 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 CTE récursives — correctes, mais lentes sur des arbres profonds et difficiles à composer.

Les tables de fermeture résolvent cela en précalculant et en stockant l’ensemble des relations entre ancêtres et descendants dans l’arbre. Chaque paire ancêtre-descendant est enregistrée explicitement, avec la profondeur, au moment de l’écriture. On obtient ainsi des lectures nettement plus rapides au prix 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 un lien parental 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;

Cela fonctionne. Mais sur un arbre profond, la CTE récursive parcourt 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 CTE 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 reliant un ancêtre à un descendant : 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. Les exemples de cet article supposent un arbre strict : chaque personne a au plus un parent enregistré, de sorte que chaque paire ancêtre-descendant possède exactement un chemin et une profondeur. Les généalogies réelles avec deux parents par personne, ou dans lesquelles le même ancêtre est atteint par plusieurs lignées, nécessitent un schéma étendu (par exemple, une ligne par chemin ou la conservation de la profondeur minimale par paire). La requête LCA renvoie alors l’un des ancêtres communs les plus proches, potentiellement multiples, comme l’un des membres d’un couple d’ancêtres.

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.

Rechercher tous les ancêtres

Avec la table de fermeture en place, rechercher tous les ancêtres d’une personne ne nécessite qu’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 peut être exécutée avec un seul parcours 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 généralement beaucoup 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 schéma 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;

Plus proche ancêtre commun

Le plus proche ancêtre commun (LCA, pour Lowest Common Ancestor) 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. Grâce aux deux parcours d’index sur descendant_id, cela s’exécute en millisecondes même sur des arbres de taille moyenne. 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 ancêtre commun le plus proche.

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 avec une génération d’écart ont un degré de 5. Cette requête retourne ces valeurs correctement sans aucune logique de parcours au niveau applicatif.

La description de la relation — « cousin germain avec deux générations d’écart », « grand-oncle » — nécessite une logique supplémentaire qui associe les valeurs de profondeur à des libellés de parenté. Une fonction qui prend la profondeur de la personne A au LCA et la profondeur de la personne B au LCA et retourne un libellé de parenté couvre la plupart des cas courants. Cette logique relève de la couche applicative, pas du SQL, et c’est considérablement plus simple quand les valeurs de profondeur sont disponibles comme des entiers directement exploitables issus de 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 lien parental 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, cela ne suffit pas : les lignes qui relient ses ancêtres à ces descendants doivent également être supprimées, sinon la table de fermeture continue d’indiquer qu’ils sont apparentés. Une fois ces lignes supprimées, les descendants sont déconnectés de l’ensemble d’ancêtres de la personne. La pertinence de ce comportement 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 un lien parental — remplacer un parent enregistré par une autre personne — nécessite de supprimer les anciennes lignes de fermeture pour le sous-arbre dont l’enfant est la racine 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, où les écritures sont peu fréquentes, c’est acceptable.

Comparaison des performances

La différence de performance entre les tables de fermeture et les CTE 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 CTE récursives prend assez de temps pour paraître légèrement lente dans une interface utilisateur. 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.

Le surcroît d’écritures lié à la maintenance 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 6 500 lignes (environ 13 par personne, en comptant chaque autoréférence). Même en tenant compte du surcoût par ligne de PostgreSQL (un en-tête de tuple de 23 octets plus un pointeur de ligne) et des trois index, cela représente de l’ordre d’une centaine d’octets par ligne, soit moins d’un mégaoctet au total. 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 recherches par index rapides.

Analyses connexes

Pour aller plus loin

Hetzner Cloud fin 2026 : offres et tarifs pour auto-héberger n8n, Windmill, Twenty et Ollama

Accès à l'API Google Ads en 2026 : les projets Cloud remplacent les Developer Tokens

TaxStayTracker : un relevé plus clair de vos jours de voyage