tva
← Insights

Tabelas de Fechamento para Cálculo de Relacionamentos

As consultas de relacionamento familiar são enganosamente difíceis. “Essas duas pessoas estão relacionadas?” “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 recursivos — correto, mas lento em árvores profundas e difícil de compor.

As tabelas de fechamento resolvem isso pré-computando e armazenando a acessibilidade completa da árvore. Cada par ancestral-descendente é registrado explicitamente, com profundidade, no momento da escrita. O resultado são leituras dramaticamente 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 troca está quase sempre correta.

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 simples de escrever. Inserir uma nova pessoa requer uma linha. Atualizar um relacionamento de pai 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 um CTE recursivo:

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, o CTE recursivo escaneia 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 dois CTEs recursivos para uma consulta como “encontrar o ancestral comum de X e Y” requer rodar ambas as recursões e então juntar os resultados, o que compõe 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 um relacionamento de acessibilidade: 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.

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 existe sem pai, 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 em vigor, 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 é 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, isso é uma ordem de magnitude mais rápido do que o CTE recursivo equivalente, e a diferença cresce conforme a árvore 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 Baixo

O Ancestral Comum Mais Baixo (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, isso roda em milissegundos mesmo em árvores moderadamente grandes. Não há recursão, nenhuma passagem múltipla 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 agregado 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 em primeiro grau ascendente têm um grau de 5. Essa consulta retorna esses valores corretamente sem nenhuma lógica de travessia na camada de aplicação.

A descrição do relacionamento — “primo de segundo grau”, “tio-avô” — requer lógica adicional que mapeia os valores de profundidade para rótulos de relacionamento. Uma função que pega 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 limpos da 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, esses descendentes estão agora 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 é tipicamente evitado 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 reinserindo-as em relação ao novo pai. A implementação mais simples é uma transação que exclui todas as linhas de fechamento para a subárvore afetada inteira e as reinserindo 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 recursivos é 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 recursivos roda em uma faixa que a faz parecer um pouco lenta em um contexto de UI. 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 única pessoa adicionada. A troca favorece fortemente a abordagem de tabela de fechamento.

A sobrecarga de armazenamento também vale a pena notar. Uma tabela de fechamento para uma árvore de 500 pessoas com profundidade média de 12 armazena aproximadamente 3.000 a 5.000 linhas. Com alguns bytes por linha, isso é insignificante. 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 estará em cache e disponível para pesquisas de índice rápidas.

Insights Relacionados

Artigos relacionados

Reduzindo Taxas de Devolução no Amazon FBA com Análise Sistemática de Dados

Corrigindo SEO Após uma Migração do WordPress para Astro: Cadeias de Redirecionamento, Sitemaps e Limpeza no GSC

n8n vs Zapier: Uma Avaliação Honesta de um Desenvolvedor