tva
← Approfondimenti

Closure table per il calcolo delle relazioni

Le query sulle relazioni familiari sono più difficili di quanto sembri. «Queste due persone sono imparentate?» «Qual è il nostro grado di separazione?» «Chi è l’antenato comune più vicino?» Sono domande naturali per una persona, ma onerose da risolvere con la normale archiviazione tramite lista di adiacenza, in cui ogni riga registra soltanto una coppia diretta genitore-figlio. Per rispondere occorre attraversare l’albero ricorsivamente, il che in SQL significa usare CTE ricorsive: corrette, ma lente su alberi profondi e difficili da combinare.

Le closure table risolvono il problema precalcolando e memorizzando tutte le relazioni di raggiungibilità dell’albero. Ogni coppia antenato-discendente viene registrata esplicitamente, insieme alla profondità, al momento della scrittura. Il risultato sono letture molto più veloci, a costo di scritture più complesse. Per un’applicazione di alberi genealogici, in cui le letture sono molto più frequenti delle scritture, questo compromesso è quasi sempre appropriato.

Il problema della lista di adiacenza

Il modo standard di archiviare un albero in un database relazionale è una lista di adiacenza: una tabella in cui ogni riga contiene un id e un parent_id. È semplice da comprendere e da aggiornare. Inserire una nuova persona richiede una riga. Modificare una relazione genitoriale richiede un aggiornamento.

Ma rispondere alla domanda «Chi sono tutti gli antenati della persona X?» richiede di risalire l’albero ricorsivamente. In PostgreSQL e nella maggior parte dei database SQL moderni, questa operazione si esprime con una CTE ricorsiva:

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;

Funziona. Su un albero profondo, però, la CTE ricorsiva esamina le righe a ogni livello e il costo cresce con la profondità dell’albero. Per un albero poco profondo, di tre o quattro generazioni, è sufficientemente veloce. Per un albero che comprende dieci o quindici generazioni e centinaia di nodi, le prestazioni peggiorano sensibilmente. Inoltre, combinare due CTE ricorsive per una query come «Trova l’antenato comune di X e Y» richiede di eseguire entrambe le ricorsioni e poi unire i risultati, aumentando ulteriormente il costo.

La struttura della closure table

Una closure table affianca una seconda tabella alla tabella principale delle persone. Ogni riga della closure table rappresenta una relazione di raggiungibilità: una coppia (ancestor_id, descendant_id), più la profondità, ossia il numero di archi che le separano. Ogni persona è anche antenata di sé stessa a profondità zero. Gli esempi di questo articolo presuppongono un albero in senso stretto: ogni persona ha al massimo un genitore registrato, quindi ogni coppia antenato-discendente ha esattamente un percorso e una profondità. Le genealogie reali con due genitori per persona, o in cui si raggiunge lo stesso antenato attraverso più linee, richiedono uno schema esteso (per esempio, una riga per percorso oppure la profondità minima per coppia); la query LCA restituisce quindi uno dei possibili antenati comuni più vicini, come uno dei membri di una coppia di antenati.

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

Quando la persona X esiste senza un genitore, viene inserita una riga: (X, X, 0). Quando la persona X viene aggiunta come figlia della persona P, l’inserimento si estende a tutti gli antenati di 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;

Questo significa che inserire una persona alla profondità generazionale N richiede l’inserimento di N+1 righe nella closure table. Per un albero genealogico tipico, la cui profondità supera raramente le 15 o 20 generazioni, è un carico del tutto gestibile. Il costo aggiuntivo delle scritture è proporzionale alla profondità, non alle dimensioni totali dell’albero.

Query su tutti gli antenati

Con la closure table, recuperare tutti gli antenati di una persona richiede un solo join, senza ricorsione:

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;

Questa query può essere eseguita con un’unica scansione dell’indice su descendant_id. Il costo è proporzionale al numero di antenati, non alla profondità dell’albero. Per un albero di profondità genealogica tipica, è in genere molto più veloce della CTE ricorsiva equivalente, e la differenza aumenta al crescere della profondità.

La query simmetrica, che recupera tutti i discendenti di una persona, segue lo stesso schema usando l’indice su 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;

L’antenato comune più vicino

L’antenato comune più vicino (Lowest Common Ancestor, LCA) di due persone è l’antenato più recente che hanno in comune. In termini genealogici, risponde alla domanda «Chi è l’antenato comune più recente di questi due individui?»: un nonno, un bisnonno o un antenato ancora precedente, a seconda della relazione.

Con una closure table, la query LCA esegue un join sui due insiemi di antenati, seleziona quelli comuni e li ordina per profondità per trovare il più vicino:

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;

La query restituisce l’antenato comune con la minore distanza complessiva dalle due persone. Grazie alle due scansioni dell’indice su descendant_id, viene eseguita in millisecondi anche su alberi di dimensioni moderatamente grandi. Non richiede ricorsione, passaggi multipli attraverso l’albero né materializzazioni intermedie degli insiemi di antenati oltre a quanto fornito dall’indice.

La query gestisce naturalmente anche i casi in cui una persona è antenata dell’altra. Se la persona A è un’antenata diretta della persona B, l’LCA è A stessa, e la query la restituisce correttamente perché A appartiene al proprio insieme di antenati a profondità 0.

Grado di separazione

Il grado di separazione tra due persone è il numero di archi familiari da attraversare per passare dall’una all’altra tramite il loro antenato comune. Non coincide con la differenza di profondità tra loro: è la somma delle distanze di ciascuna persona dal rispettivo 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;

È lo stesso join della query LCA, con l’aggregazione MIN() al posto di ORDER BY ... LIMIT 1. I cugini di primo grado hanno un grado di separazione di 4, perché entrambi distano due passi da un nonno comune. Un cugino di primo grado e il figlio dell’altro cugino hanno un grado di separazione di 5. Questa query restituisce correttamente tali valori senza alcuna logica di attraversamento a livello applicativo.

La descrizione della parentela, come «cugino di primo grado con due generazioni di differenza» o «prozio», richiede una logica aggiuntiva che associ i valori di profondità alle denominazioni delle relazioni. Una funzione che riceve la profondità dalla persona A all’LCA e quella dalla persona B all’LCA e restituisce una denominazione della parentela copre i casi più comuni. È logica applicativa, non SQL, ed è molto più semplice quando la query fornisce le profondità come valori interi ben definiti.

Mantenere la closure table durante gli aggiornamenti

Gli inserimenti sono semplici, come mostrato sopra. Le eliminazioni e le modifiche alle relazioni genitoriali richiedono maggiore attenzione.

Eliminare una persona dall’albero significa rimuovere tutte le righe della closure table in cui compare come antenata o discendente. Se la persona ha discendenti, questo da solo non basta: occorre rimuovere anche le righe che collegano i suoi antenati a quei discendenti, altrimenti la closure table continua a indicarli come imparentati. Una volta rimosse queste righe, i discendenti risultano scollegati dall’insieme di antenati della persona. La correttezza di questo comportamento dipende dall’applicazione: in ambito genealogico, l’eliminazione di una persona con discendenti registrati viene in genere impedita a livello applicativo.

Modificare una relazione genitoriale, correggendo il genitore registrato con un’altra persona, richiede di rimuovere le vecchie righe della closure table per il sottoalbero che ha come radice il figlio e di reinserirle rispetto al nuovo genitore. L’implementazione più semplice è una transazione che elimina tutte le righe della closure table per l’intero sottoalbero interessato e le reinserisce attraversando l’albero a partire dal nuovo genitore. È corretta, ma blocca le righe interessate durante la transazione. Per la maggior parte delle applicazioni genealogiche, che eseguono poche scritture, è accettabile.

Confronto delle prestazioni

La differenza di prestazioni tra closure table e CTE ricorsive è significativa e cresce con le dimensioni dell’albero. Su un albero sintetico con 500 nodi e una profondità media di 12 generazioni, una query LCA con CTE ricorsive richiede un tempo che la rende leggermente lenta nell’interfaccia utente. La stessa query con il join della closure table è abbastanza veloce da far dipendere la latenza soprattutto dal tempo di andata e ritorno della rete, anziché dall’esecuzione della query.

Il mantenimento della closure table aggiunge a ogni inserimento un costo di scrittura misurabile, proporzionale alla profondità dell’albero. In un contesto genealogico, però, gli inserimenti sono rari rispetto alle letture: per ogni persona aggiunta, un albero genealogico può essere interrogato migliaia di volte per visualizzare relazioni e rappresentazioni grafiche. Il compromesso favorisce nettamente l’approccio con closure table.

Va considerato anche lo spazio di archiviazione aggiuntivo. Una closure table per un albero di 500 persone con profondità media di 12 contiene circa 6.500 righe (circa 13 per persona, incluso ciascun autoriferimento). Anche considerando lo spazio aggiuntivo richiesto da PostgreSQL per ogni riga (un’intestazione di tupla di 23 byte più un puntatore di riga) e i tre indici, si tratta di un ordine di grandezza di cento byte per riga, ovvero meno di un megabyte in totale. Anche un database genealogico molto grande, con decine di migliaia di individui, produce una closure table che entra agevolmente nella memoria di un moderno server database, dove viene mantenuta in cache e resa disponibile per ricerche rapide tramite indice.

Approfondimenti correlati

Per approfondire

Hetzner Cloud a fine 2026: piani e prezzi per il self-hosting di n8n, Windmill, Twenty e Ollama

Accesso alla Google Ads API nel 2026: i progetti Cloud sostituiscono i Developer Token

TaxStayTracker: un registro più chiaro dei giorni di viaggio