Tabelas de fechamento para calcular relações de parentesco

Consultas de parentesco são mais difíceis do que parecem. “Essas duas pessoas têm parentesco?” “Qual é o nosso grau de separação?” “Quem é o ancestral comum mais próximo?” Essas perguntas parecem naturais para uma pessoa, mas são custosas de responder com armazenamento de lista de adjacência padrão, onde cada linha registra apenas um par direto pai-filho. Respondê-las requer percorrer a árvore recursivamente, o que em SQL significa CTEs recursivas — uma solução correta, mas lenta em árvores profundas e difícil de combinar.

As tabelas de fechamento resolvem isso pré-computando e armazenando todas as relações de alcançabilidade da árvore. Cada par ancestral-descendente é registrado explicitamente, com profundidade, no momento da gravação. O resultado são leituras muito mais rápidas ao custo de escritas mais complexas. Para uma aplicação de árvore genealógica onde as leituras são muito mais frequentes do que as escritas, essa compensação quase sempre vale a pena.

O problema da lista de adjacência

A maneira padrão de armazenar uma árvore em um banco de dados relacional é uma lista de adjacência: uma tabela onde cada linha tem um id e um parent_id. É simples de entender e de gravar. Inserir uma nova pessoa requer uma linha. Atualizar um vínculo parental requer uma atualização.

Mas responder “quem são todos os ancestrais da pessoa X?” requer percorrer a árvore recursivamente. No PostgreSQL e na maioria dos bancos de dados SQL modernos, isso é expresso com uma 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;

Isso funciona. Mas, em uma árvore profunda, a CTE recursiva varre linhas em cada nível e o custo cresce com a profundidade da árvore. Para uma árvore rasa — três ou quatro gerações — é rápido o suficiente. Para uma árvore que abrange dez ou quinze gerações com centenas de nós, o desempenho degrada visivelmente. Pior, compor duas CTEs recursivas para uma consulta como “encontrar o ancestral comum de X e Y” requer executar ambas as recursões e então juntar os resultados, o que aumenta ainda mais o custo.

A estrutura da tabela de fechamento

Uma tabela de fechamento adiciona uma segunda tabela ao lado da tabela principal de pessoas. Cada linha na tabela de fechamento representa uma relação de alcançabilidade: um par de (ancestor_id, descendant_id), mais a profundidade (número de arestas entre eles). Cada pessoa também é sua própria ancestral na profundidade zero. Os exemplos deste artigo pressupõem uma árvore estrita: cada pessoa tem no máximo um progenitor registrado, de modo que cada par ancestral-descendente tem exatamente um caminho e uma profundidade. Genealogias reais com dois progenitores por pessoa, ou em que o mesmo ancestral é alcançado por várias linhagens, precisam de um esquema estendido (por exemplo, uma linha por caminho ou a manutenção da profundidade mínima por par), e a consulta de LCA passa a retornar um entre possivelmente vários ancestrais comuns mais próximos, como um dos membros de um casal ancestral.

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 a pessoa X não tem um vínculo parental registrado, uma linha é inserida: (X, X, 0). Quando a pessoa X é adicionada como filha da pessoa P, a inserção se expande para incluir todos os ancestrais de P:

-- Auto-referência
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
VALUES (:x_id, :x_id, 0);

-- Todos os ancestrais do pai P tornam-se ancestrais de X, na profundidade + 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;

Isso significa que inserir uma pessoa na profundidade de geração N requer inserir N+1 linhas na tabela de fechamento. Para uma árvore genealógica típica, onde a profundidade raramente excede 15 ou 20 gerações, isso é totalmente gerenciável. A sobrecarga de escrita é proporcional à profundidade, não ao tamanho total da árvore.

Consultando todos os ancestrais

Com a tabela de fechamento implementada, consultar todos os ancestrais de uma pessoa é um único join sem recursão:

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;

Essa consulta pode ser executada com uma única varredura de índice em descendant_id. O custo é proporcional ao número de ancestrais, não à profundidade da árvore. Para uma árvore de profundidade genealógica típica, a execução costuma ser muito mais rápida do que uma CTE recursiva equivalente, e a diferença cresce à medida que a árvore se aprofunda.

A consulta simétrica — todos os descendentes de uma pessoa — segue o mesmo padrão usando o índice 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;

Ancestral comum mais próximo

O ancestral comum mais próximo (LCA) de duas pessoas é o ancestral mais recente que compartilham. Em termos de árvore genealógica, é a resposta para “quem é o ancestral comum mais recente desses dois indivíduos?” — o avô, ou bisavô, ou mais distante, dependendo do relacionamento.

Com uma tabela de fechamento, a consulta LCA é um join nos dois conjuntos de ancestrais, filtrado para ancestrais compartilhados, ordenado por profundidade para encontrar o mais próximo:

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;

Isso retorna o ancestral compartilhado com a menor distância combinada de ambas as pessoas. Nas duas varreduras de índice em descendant_id, a consulta é executada em milissegundos mesmo em árvores moderadamente grandes. Não há recursão, não há múltiplas passagens pela árvore e nenhuma materialização intermediária de conjuntos de ancestrais além do que o índice fornece.

A consulta também lida naturalmente com casos onde uma pessoa é ancestral da outra. Se a pessoa A é ancestral direta da pessoa B, o LCA é a própria pessoa A, e a consulta a retorna corretamente porque A está em seu próprio conjunto de ancestrais na profundidade 0.

Grau de separação

O grau de separação entre duas pessoas é o número de arestas familiares que você precisa percorrer para ir de uma para a outra via seu ancestral compartilhado. Não é o mesmo que a diferença de profundidade entre elas — é a soma da distância de cada pessoa ao seu 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;

Este é o mesmo join da consulta LCA com a agregação MIN() em vez de ORDER BY ... LIMIT 1. Primos de primeiro grau têm um grau de separação de 4 (ambos estão a dois passos de um avô compartilhado). Primos de primeiro grau com uma geração de diferença têm um grau de 5. Essa consulta retorna esses valores corretamente sem nenhuma lógica de percurso na camada de aplicação.

A descrição do relacionamento — “primo de primeiro grau com duas gerações de diferença”, “tio-avô” — requer lógica adicional que mapeia os valores de profundidade para rótulos de relacionamento. Uma função que recebe a profundidade da pessoa A ao LCA e a profundidade da pessoa B ao LCA e retorna um rótulo de relacionamento cobre a maioria dos casos comuns. Isso é lógica da camada de aplicação, não SQL, e é consideravelmente mais simples quando os valores de profundidade estão disponíveis como inteiros bem definidos retornados pela consulta.

Mantendo a tabela de fechamento em atualizações

As inserções são diretas, como mostrado acima. As exclusões e as mudanças de relacionamento pai-filho requerem mais cuidado.

Excluir uma pessoa da árvore significa remover todas as linhas na tabela de fechamento onde ela aparece como ancestral ou descendente. Se a pessoa tem descendentes, só isso não basta: as linhas que ligam os ancestrais da pessoa a esses descendentes também precisam ser removidas; caso contrário, a tabela de fechamento continua indicando que eles são parentes. Depois que essas linhas são removidas, os descendentes ficam desconectados do conjunto de ancestrais da pessoa. Se esse é o comportamento correto depende da aplicação — em um contexto genealógico, excluir uma pessoa que tem descendentes registrados é normalmente impedido na camada de aplicação.

Mudar um relacionamento pai-filho — corrigir um pai registrado para uma pessoa diferente — requer remover as linhas de fechamento antigas para a subárvore enraizada no filho e reinseri-las em relação ao novo pai. A implementação mais simples é uma transação que exclui todas as linhas de fechamento para toda a subárvore afetada e as reinsere percorrendo a partir do novo pai. Isso está correto, mas bloqueia as linhas relevantes durante a transação. Para a maioria das aplicações genealógicas, que têm poucas escritas, isso é aceitável.

Comparação de desempenho

A diferença de desempenho entre tabelas de fechamento e CTEs recursivas é significativa e cresce com o tamanho da árvore. Em uma árvore sintética com 500 nós e 12 gerações de profundidade média, uma consulta LCA usando CTEs recursivas tem um tempo de execução que parece um pouco lento na interface. A mesma consulta usando o join da tabela de fechamento é rápida o suficiente para que a latência seja dominada pelo tempo de ida e volta na rede em vez do tempo de execução da consulta.

A sobrecarga de escrita de manter a tabela de fechamento adiciona um custo mensurável por inserção, proporcional à profundidade da árvore. Mas em um contexto de árvore genealógica, as inserções são raras em relação às leituras — uma árvore genealógica pode ser consultada milhares de vezes para exibir relacionamentos e visualizações para cada pessoa adicionada. Essa compensação favorece fortemente a abordagem de tabela de fechamento.

A sobrecarga de armazenamento também merece atenção. Uma tabela de fechamento para uma árvore de 500 pessoas com profundidade média de 12 armazena aproximadamente 6.500 linhas (cerca de 13 por pessoa, incluindo cada autorreferência). Mesmo considerando a sobrecarga por linha do PostgreSQL (um cabeçalho de tupla de 23 bytes mais um ponteiro de linha) e os três índices, isso fica na ordem de cem bytes por linha, ou menos de um megabyte no total. Mesmo um banco de dados genealógico muito grande com dezenas de milhares de indivíduos produz uma tabela de fechamento que cabe confortavelmente na memória em um servidor de banco de dados moderno, onde ficará em cache e disponível para consultas rápidas por índice.