Tablas de cierre para el cálculo de relaciones

Las consultas sobre relaciones familiares son más difíciles de lo que parecen. «¿Estas dos personas son parientes?», «¿Cuál es nuestro grado de separación?», «¿Quién es el antepasado común más cercano?». Son preguntas naturales para una persona, pero costosas de responder con el almacenamiento habitual mediante listas de adyacencia, donde cada fila registra únicamente una relación directa entre progenitor e hijo. Responderlas exige recorrer el árbol de forma recursiva, lo que en SQL implica CTE recursivas: una solución correcta, pero lenta en árboles profundos y difícil de combinar.

Las tablas de cierre resuelven este problema calculando y almacenando de antemano todas las relaciones de alcanzabilidad del árbol. Cada par antepasado-descendiente se registra explícitamente, junto con su profundidad, al escribir los datos. El resultado son lecturas mucho más rápidas a costa de escrituras más complejas. En una aplicación de árboles genealógicos, donde las lecturas son mucho más frecuentes que las escrituras, esta contrapartida casi siempre es la adecuada.

El problema de las listas de adyacencia

La forma habitual de almacenar un árbol en una base de datos relacional es una lista de adyacencia: una tabla en la que cada fila tiene un id y un parent_id. Es fácil de entender y de escribir. Insertar una nueva persona requiere una fila. Modificar una relación con un progenitor requiere una actualización.

Pero responder «¿quiénes son todos los antepasados de la persona X?» exige recorrer el árbol hacia arriba de forma recursiva. En PostgreSQL y en la mayoría de las bases de datos SQL modernas, esto se expresa mediante una CTE recursiva:

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;

Funciona. Sin embargo, en un árbol profundo, la CTE recursiva examina filas en cada nivel y el costo aumenta con la profundidad del árbol. En uno poco profundo —tres o cuatro generaciones— es suficientemente rápida. En un árbol de diez o quince generaciones con cientos de nodos, el rendimiento se degrada de forma perceptible. Además, combinar dos CTE recursivas para una consulta como «encontrar el antepasado común de X e Y» exige ejecutar ambas recursiones y unir sus resultados, lo que aumenta el costo.

La estructura de una tabla de cierre

Una tabla de cierre añade una segunda tabla junto a la tabla principal de personas. Cada fila representa una relación de alcanzabilidad: un par (ancestor_id, descendant_id) más la profundidad, es decir, el número de aristas entre ambos. Cada persona también es su propio antepasado con profundidad cero. Los ejemplos de este artículo suponen un árbol estricto: cada persona tiene como máximo un progenitor registrado, por lo que cada par de antepasado y descendiente tiene exactamente un camino y una profundidad. Las genealogías reales con dos progenitores por persona, o en las que se llega al mismo antepasado por varias líneas, necesitan un esquema ampliado (por ejemplo, una fila por camino o la profundidad mínima por par), y la consulta de LCA devuelve entonces uno de los posibles antepasados comunes más cercanos, como un miembro de una pareja de antepasados.

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

Cuando la persona X existe sin un progenitor, se inserta una fila: (X, X, 0). Cuando se añade a X como hijo de la persona P, la inserción se amplía para incluir a todos los antepasados de 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;

Esto significa que insertar una persona a una profundidad generacional N exige insertar N+1 filas en la tabla de cierre. En un árbol genealógico típico, cuya profundidad rara vez supera las 15 o 20 generaciones, es perfectamente manejable. La carga adicional de escritura es proporcional a la profundidad, no al tamaño total del árbol.

Consultar todos los antepasados

Con la tabla de cierre, consultar todos los antepasados de una persona requiere una sola unión, sin recursión:

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;

Esta consulta puede ejecutarse con un único recorrido del índice de descendant_id. El costo es proporcional al número de antepasados, no a la profundidad del árbol. En un árbol de profundidad genealógica típica, suele ser mucho más rápida que la CTE recursiva equivalente, y la diferencia aumenta a medida que el árbol se hace más profundo.

La consulta simétrica —todos los descendientes de una persona— sigue el mismo patrón con el índice de 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;

El antepasado común más cercano

El antepasado común más cercano (LCA, por sus siglas en inglés) de dos personas es el antepasado más reciente que comparten. En un árbol genealógico, responde a «¿quién es el antepasado común más reciente de estas dos personas?»: un abuelo, un bisabuelo o alguien de una generación anterior, según la relación.

Con una tabla de cierre, la consulta del LCA une los dos conjuntos de antepasados, selecciona los compartidos y los ordena por profundidad para encontrar el más cercano:

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;

Devuelve el antepasado compartido con la menor distancia combinada respecto a ambas personas. Con los dos recorridos del índice de descendant_id, se ejecuta en milisegundos incluso en árboles de tamaño considerable. No hay recursión, múltiples recorridos del árbol ni materialización intermedia de conjuntos de antepasados más allá de lo que proporciona el índice.

La consulta también contempla de forma natural los casos en que una persona es antepasada de la otra. Si la persona A es antepasada directa de B, el LCA es la propia A, y la consulta la devuelve correctamente porque A pertenece a su propio conjunto de antepasados con profundidad 0.

Grado de separación

El grado de separación entre dos personas es el número de aristas de parentesco que hay que recorrer para pasar de una a otra a través de su antepasado común. No es lo mismo que la diferencia de profundidad entre ambas: es la suma de la distancia de cada persona a su 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;

Es la misma unión que en la consulta del LCA, con la función de agregación MIN() en lugar de ORDER BY ... LIMIT 1. Los primos hermanos tienen un grado de separación de 4: ambos están a dos pasos de un abuelo compartido. Una persona y el hijo de su primo hermano tienen un grado de 5. La consulta devuelve correctamente esos valores sin lógica de recorrido en la capa de aplicación.

La descripción del parentesco —«primo hermano con dos generaciones de diferencia», «tío abuelo»— requiere lógica adicional que convierta los valores de profundidad en etiquetas de parentesco. Una función que reciba la profundidad de la persona A al LCA y de la persona B al LCA y devuelva una etiqueta cubre la mayoría de los casos habituales. Esta lógica pertenece a la capa de aplicación, no a SQL, y es mucho más sencilla cuando la consulta proporciona las profundidades como enteros claros.

Mantener la tabla de cierre al actualizar datos

Las inserciones son sencillas, como se mostró anteriormente. Las eliminaciones y los cambios en las relaciones con progenitores requieren más cuidado.

Eliminar una persona del árbol implica quitar todas las filas de la tabla de cierre en las que aparezca como antepasada o descendiente. Si tiene descendientes, eso por sí solo no basta: también hay que eliminar las filas que vinculan a los antepasados de esa persona con esos descendientes; de lo contrario, la tabla de cierre seguirá indicando que están emparentados. Una vez eliminadas esas filas, los descendientes quedan desconectados del conjunto de antepasados de esa persona. Que ese comportamiento sea correcto depende de la aplicación: en un contexto genealógico, normalmente la capa de aplicación impide eliminar a una persona con descendientes registrados.

Cambiar una relación con un progenitor —corregir el progenitor registrado para que sea otra persona— exige eliminar las filas de cierre antiguas del subárbol cuya raíz es el hijo y volver a insertarlas con respecto al nuevo progenitor. La implementación más sencilla es una transacción que elimina todas las filas de cierre del subárbol afectado y las vuelve a insertar recorriendo el árbol desde el nuevo progenitor. Es correcta, pero bloquea las filas pertinentes durante la transacción. En la mayoría de las aplicaciones genealógicas, con pocas escrituras, resulta aceptable.

Comparación del rendimiento

La diferencia de rendimiento entre las tablas de cierre y las CTE recursivas es considerable y aumenta con el tamaño del árbol. En un árbol sintético de 500 nodos y una profundidad media de 12 generaciones, una consulta del LCA con CTE recursivas tarda lo suficiente para percibirse algo lenta en una interfaz. La misma consulta mediante la unión de la tabla de cierre es tan rápida que la latencia depende principalmente del tiempo de ida y vuelta de la red, no de la ejecución de la consulta.

Mantener la tabla de cierre añade un costo medible por inserción, proporcional a la profundidad del árbol. Sin embargo, en un árbol genealógico las inserciones son poco frecuentes frente a las lecturas: por cada persona añadida, el árbol puede consultarse miles de veces para mostrar relaciones y visualizaciones. La contrapartida favorece claramente las tablas de cierre.

También conviene considerar el almacenamiento adicional. Una tabla de cierre para un árbol de 500 personas con una profundidad media de 12 almacena aproximadamente 6 500 filas (unas 13 por persona, incluida cada autorreferencia). Incluso teniendo en cuenta la sobrecarga por fila de PostgreSQL (una cabecera de tupla de 23 bytes más un puntero de línea) y los tres índices, el almacenamiento es del orden de cien bytes por fila, o menos de un megabyte en total. Incluso una base de datos genealógica muy grande, con decenas de miles de personas, genera una tabla de cierre que cabe holgadamente en la memoria de un servidor de bases de datos moderno, donde se almacena en caché y permite búsquedas rápidas por índice.