CTEs recursivas: hierarquias e grafos

1. Introdução às CTEs Recursivas

As Common Table Expressions (CTEs) recursivas são uma das ferramentas mais poderosas do SQL moderno para trabalhar com dados hierárquicos e grafos. Diferentemente das CTEs comuns, que funcionam como views temporárias, as CTEs recursivas têm a capacidade de referenciar a si mesmas, permitindo percorrer estruturas de profundidade variável de forma elegante e eficiente.

A sintaxe básica de uma CTE recursiva segue este padrão:

WITH RECURSIVE nome_cte AS (
    -- Membro âncora
    SELECT ...
    UNION ALL
    -- Membro recursivo
    SELECT ...
    FROM nome_cte
    WHERE condição_de_parada
)
SELECT * FROM nome_cte;

A principal diferença entre CTEs comuns e recursivas está na capacidade de auto-referência. Enquanto CTEs comuns são avaliadas uma única vez, as recursivas executam o membro recursivo repetidamente até que nenhuma nova linha seja produzida ou uma condição de parada seja atingida.

2. Componentes de uma CTE Recursiva

Toda CTE recursiva possui três componentes essenciais:

Membro âncora: É a consulta inicial que retorna o ponto de partida da recursão. Sem ele, não haveria base para começar o percurso.

Membro recursivo: É a consulta que referencia a própria CTE, permitindo que os resultados anteriores sejam usados para gerar novos resultados. Este membro é executado repetidamente.

Terminação: O processo recursivo termina quando o membro recursivo não retorna mais linhas. O uso de UNION ALL é obrigatório para combinar os resultados de cada iteração.

WITH RECURSIVE numeros AS (
    -- Âncora
    SELECT 1 AS num
    UNION ALL
    -- Recursivo
    SELECT num + 1
    FROM numeros
    WHERE num < 10
)
SELECT * FROM numeros;

3. Modelagem de Hierarquias no Banco de Dados

O modelo mais comum para representar hierarquias em bancos de dados relacionais é a lista de adjacência, onde cada registro possui uma referência ao seu registro pai. Considere a tabela employees:

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    manager_id INT REFERENCES employees(id)
);

INSERT INTO employees VALUES
(1, 'Ana CEO', NULL),
(2, 'Carlos Diretor', 1),
(3, 'Maria Gerente', 2),
(4, 'João Analista', 3),
(5, 'Pedro Estagiário', 4),
(6, 'Lucia Diretora', 1),
(7, 'Rui Gerente', 6);

Sem recursão, consultar todos os subordinados de um gerente exigiria múltiplos JOINs ou consultas aninhadas complexas, tornando o código praticamente inviável para hierarquias profundas.

4. Percorrendo Hierarquias (Árvores) com CTEs Recursivas

Exemplo Top-Down: Listar subordinados de um gerente

WITH RECURSIVE subordinados AS (
    -- Âncora: ponto de partida
    SELECT id, name, manager_id, 0 AS nivel
    FROM employees
    WHERE id = 2  -- Carlos Diretor

    UNION ALL

    -- Recursivo: encontra subordinados diretos
    SELECT e.id, e.name, e.manager_id, s.nivel + 1
    FROM employees e
    JOIN subordinados s ON e.manager_id = s.id
)
SELECT * FROM subordinados ORDER BY nivel, name;

Resultado:

id | name            | manager_id | nivel
---|-----------------|------------|------
2  | Carlos Diretor  | 1          | 0
3  | Maria Gerente   | 2          | 1
6  | Lucia Diretora  | 1          | 1
4  | João Analista   | 3          | 2
7  | Rui Gerente     | 6          | 2
5  | Pedro Estagiário| 4          | 3

Exemplo Bottom-Up: Caminho até o CEO

WITH RECURSIVE caminho_ceo AS (
    SELECT id, name, manager_id, CAST(name AS TEXT) AS caminho
    FROM employees
    WHERE id = 5  -- Pedro Estagiário

    UNION ALL

    SELECT e.id, e.name, e.manager_id, 
           c.caminho || ' -> ' || e.name
    FROM employees e
    JOIN caminho_ceo c ON e.id = c.manager_id
)
SELECT * FROM caminho_ceo;

5. CTEs Recursivas para Grafos

Grafos podem ser modelados com uma tabela de arestas:

CREATE TABLE arestas (
    origem INT,
    destino INT,
    PRIMARY KEY (origem, destino)
);

INSERT INTO arestas VALUES
(1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (2, 5);

Encontrar todos os caminhos entre dois nós

WITH RECURSIVE caminhos AS (
    -- Âncora: arestas diretas
    SELECT origem, destino, 
           CAST(origem || '->' || destino AS TEXT) AS caminho,
           1 AS profundidade
    FROM arestas
    WHERE origem = 1

    UNION ALL

    -- Recursivo: estende o caminho
    SELECT a.origem, a.destino,
           c.caminho || '->' || a.destino,
           c.profundidade + 1
    FROM arestas a
    JOIN caminhos c ON c.destino = a.origem
    WHERE c.caminho NOT LIKE '%' || a.destino || '%'  -- Previne ciclos
)
SELECT * FROM caminhos WHERE destino = 5;

Prevenção de loops: A condição WHERE c.caminho NOT LIKE '%' || a.destino || '%' verifica se o nó destino já foi visitado, evitando ciclos infinitos.

6. Boas Práticas e Armadilhas Comuns

Limitação de profundidade máxima

Em bancos como SQL Server, use a dica MAXRECURSION:

WITH RECURSIVE hierarquia AS (
    ...
)
SELECT * FROM hierarquia
OPTION (MAXRECURSION 10);  -- SQL Server

No PostgreSQL, MySQL e SQLite, controle manualmente com uma coluna de nível:

WITH RECURSIVE hierarquia AS (
    SELECT id, name, manager_id, 0 AS nivel
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.id, e.name, e.manager_id, h.nivel + 1
    FROM employees e
    JOIN hierarquia h ON e.manager_id = h.id
    WHERE h.nivel < 20  -- Profundidade máxima
)
SELECT * FROM hierarquia;

Performance e explosão combinatória

Em grafos densos, o número de caminhos possíveis cresce exponencialmente. Para grafos com muitos ciclos, considere:

  1. Limitar a profundidade máxima
  2. Usar algoritmos como BFS (Breadth-First Search) em vez de DFS
  3. Indexar adequadamente as colunas de junção (origem, destino, parent_id)

Detecção de ciclos

Sempre inclua verificação de ciclos em consultas de grafos:

WITH RECURSIVE exploracao AS (
    SELECT origem, destino, 
           ARRAY[origem, destino] AS visitados
    FROM arestas
    WHERE origem = 1

    UNION ALL

    SELECT a.origem, a.destino,
           e.visitados || a.destino
    FROM arestas a
    JOIN exploracao e ON e.destino = a.origem
    WHERE NOT a.destino = ANY(e.visitados)  -- PostgreSQL
)
SELECT * FROM exploracao;

7. Casos de Uso Avançados

Hierarquia de categorias (e-commerce)

WITH RECURSIVE categorias_tree AS (
    SELECT id, nome, id_pai, 0 AS nivel,
           CAST(nome AS TEXT) AS caminho_categoria
    FROM categorias
    WHERE id_pai IS NULL

    UNION ALL

    SELECT c.id, c.nome, c.id_pai, ct.nivel + 1,
           ct.caminho_categoria || ' > ' || c.nome
    FROM categorias c
    JOIN categorias_tree ct ON c.id_pai = ct.id
)
SELECT * FROM categorias_tree ORDER BY caminho_categoria;

Grafo de dependências (tarefas de projeto)

WITH RECURSIVE dependencias AS (
    SELECT id_tarefa, nome, 0 AS nivel,
           CAST(nome AS TEXT) AS ordem_execucao
    FROM tarefas
    WHERE id_dependencia IS NULL

    UNION ALL

    SELECT t.id_tarefa, t.nome, d.nivel + 1,
           d.ordem_execucao || ' -> ' || t.nome
    FROM tarefas t
    JOIN dependencias d ON t.id_dependencia = d.id_tarefa
)
SELECT * FROM dependencias ORDER BY nivel;

Árvore genealógica

WITH RECURSIVE arvore AS (
    SELECT id, nome, pai_id, mae_id, 0 AS geracao
    FROM pessoas
    WHERE id = 10  -- Pessoa alvo

    UNION ALL

    SELECT p.id, p.nome, p.pai_id, p.mae_id, a.geracao + 1
    FROM pessoas p
    JOIN arvore a ON p.id = a.pai_id OR p.id = a.mae_id
    WHERE a.geracao < 5
)
SELECT * FROM arvore ORDER BY geracao;

CTEs recursivas transformam consultas que seriam extremamente complexas ou impossíveis com SQL tradicional em soluções elegantes e de fácil manutenção. Dominar essa técnica é essencial para qualquer profissional que trabalhe com dados hierárquicos, desde organogramas empresariais até estruturas de categorias e grafos de dependências.

Referências