Consultas Recursivas

Autor

Douglas Braga

Algumas consultas são naturalmente recursivas: encontrar todos os pré-requisitos de uma disciplina (incluindo pré-requisitos de pré-requisitos), percorrer uma hierarquia de cargos, ou descobrir todos os nós alcançáveis em um grafo. O SQL padrão suporta isso com CTEs recursivas.

Common Table Expressions (WITH)

Antes de introduzir a recursão, revisamos as CTEs — expressões de tabela nomeadas que tornam consultas complexas mais legíveis:

-- CTE simples: disciplinas de semestre par de ENS
WITH disciplinas_par AS (
    SELECT id_disciplina, nome_disciplina, semestre
    FROM   disciplina
    WHERE  id_curso = 311
      AND  semestre % 2 = 0
)
SELECT dp.nome_disciplina, dp.semestre,
       COUNT(pr.id_prereq) AS num_prereqs
FROM   disciplinas_par dp
LEFT JOIN prereq pr ON pr.id_disciplina = dp.id_disciplina
GROUP BY dp.id_disciplina, dp.nome_disciplina, dp.semestre
ORDER BY dp.semestre, dp.nome_disciplina;
8 records
nome_disciplina semestre num_prereqs
Bases da Eng. de Software 2 2 0
Projeto Aplicado 2 - site WEB 2 0
Bases da Eng. de Software 4 4 1
Projeto Aplicado 4 - blockchain 4 1
Bases da Eng. de Software 6 6 2
Projeto Aplicado 6 - Machine Learning 6 1
Bases da Eng. de Software 8 8 1
Projeto Aplicado 8 - Sistema em Tempo Real 8 2

WITH RECURSIVE

Uma CTE recursiva define uma relação em termos de si mesma. A estrutura é sempre:

WITH RECURSIVE nome_cte(colunas) AS (
    -- Caso base: consulta inicial (não recursiva)
    SELECT ...
    UNION [ALL]
    -- Caso recursivo: referencia nome_cte
    SELECT ... FROM ... JOIN nome_cte ON ...
)
SELECT ... FROM nome_cte;

O SGBD executa a CTE iterativamente: 1. Avalia o caso base → resultado inicial R₀ 2. Avalia o caso recursivo usando R₀ → produz R₁ 3. Avalia usando R₁ → produz R₂ 4. Continua até que o caso recursivo produza um conjunto vazio 5. O resultado final é a união de todos os Rᵢ

UNION elimina duplicatas entre iterações (importante quando o grafo pode ter caminhos múltiplos para o mesmo nó). UNION ALL mantém todas as ocorrências.

Exemplo 1 — Pré-requisitos Transitivos

A tabela prereq registra relações diretas: “a disciplina X requer Y”. Para encontrar todos os pré-requisitos de uma disciplina (incluindo os transitivos), precisamos de recursão.

-- Estrutura de pré-requisitos diretos no banco
SELECT pr.id_disciplina,
       d1.nome_disciplina AS disciplina,
       pr.id_prereq,
       d2.nome_disciplina AS prerequisito
FROM   prereq pr
JOIN   disciplina d1 ON d1.id_disciplina = pr.id_disciplina
JOIN   disciplina d2 ON d2.id_disciplina = pr.id_prereq
ORDER BY pr.id_disciplina, pr.id_prereq;
Displaying records 1 - 10
id_disciplina disciplina id_prereq prerequisito
1110401 Microeconomia 2 1110201 História Econômica Geral
1110601 Economia Brasileira 1110401 Microeconomia 2
1110602 Orçamento e Finanças Públicas 1110402 Macroeconomia 2
1110801 Monografia 1110601 Economia Brasileira
1110801 Monografia 1110602 Orçamento e Finanças Públicas
2110401 Eletiva I 2110201 Desenvolvimento Humano
2110601 Eletiva II 2110401 Eletiva I
2110801 Tecnologia Educacional - Design 2110601 Eletiva II
3110401 Bases da Eng. de Software 4 3110201 Bases da Eng. de Software 2
3110402 Projeto Aplicado 4 - blockchain 3110202 Projeto Aplicado 2 - site WEB 
-- Todos os pré-requisitos transitivos de cada disciplina
WITH RECURSIVE prereqs_transitivos(id_disciplina_raiz, id_prereq, profundidade) AS (
    -- Caso base: pré-requisitos diretos
    SELECT id_disciplina, id_prereq, 1
    FROM   prereq

    UNION

    -- Caso recursivo: pré-requisitos dos pré-requisitos
    SELECT pt.id_disciplina_raiz, p.id_prereq, pt.profundidade + 1
    FROM   prereqs_transitivos pt
    JOIN   prereq p ON p.id_disciplina = pt.id_prereq
)
SELECT pt.id_disciplina_raiz                 AS disciplina_id,
       d_raiz.nome_disciplina                AS disciplina,
       pt.id_prereq                          AS prereq_id,
       d_prereq.nome_disciplina              AS prerequisito,
       pt.profundidade                       AS nivel
FROM   prereqs_transitivos pt
JOIN   disciplina d_raiz   ON d_raiz.id_disciplina   = pt.id_disciplina_raiz
JOIN   disciplina d_prereq ON d_prereq.id_disciplina = pt.id_prereq
ORDER BY disciplina, nivel, prereq_id;
Displaying records 1 - 10
disciplina_id disciplina prereq_id prerequisito nivel
3110401 Bases da Eng. de Software 4 3110201 Bases da Eng. de Software 2 1
3110601 Bases da Eng. de Software 6 3110401 Bases da Eng. de Software 4 1
3110601 Bases da Eng. de Software 6 3110402 Projeto Aplicado 4 - blockchain 1
3110601 Bases da Eng. de Software 6 3110201 Bases da Eng. de Software 2 2
3110601 Bases da Eng. de Software 6 3110202 Projeto Aplicado 2 - site WEB 2
3110801 Bases da Eng. de Software 8 3110601 Bases da Eng. de Software 6 1
3110801 Bases da Eng. de Software 8 3110401 Bases da Eng. de Software 4 2
3110801 Bases da Eng. de Software 8 3110402 Projeto Aplicado 4 - blockchain 2
3110801 Bases da Eng. de Software 8 3110201 Bases da Eng. de Software 2 3
3110801 Bases da Eng. de Software 8 3110202 Projeto Aplicado 2 - site WEB 3

A coluna nivel indica a distância: 1 = pré-requisito direto; 2 = pré-requisito do pré-requisito; e assim por diante.

Exemplo 2 — Caminho Mínimo: Quantos Semestres de Antecedência?

Combinando a recursão com MIN, podemos responder: “qual a distância máxima na cadeia de pré-requisitos de cada disciplina?”

WITH RECURSIVE prereqs_transitivos(id_disciplina_raiz, id_prereq, profundidade) AS (
    SELECT id_disciplina, id_prereq, 1
    FROM   prereq
    UNION
    SELECT pt.id_disciplina_raiz, p.id_prereq, pt.profundidade + 1
    FROM   prereqs_transitivos pt
    JOIN   prereq p ON p.id_disciplina = pt.id_prereq
)
SELECT d.nome_disciplina            AS disciplina,
       d.semestre                   AS semestre_curriculo,
       COUNT(DISTINCT pt.id_prereq) AS total_prereqs_transitivos,
       MAX(pt.profundidade)         AS profundidade_maxima
FROM   disciplina d
JOIN   prereqs_transitivos pt ON pt.id_disciplina_raiz = d.id_disciplina
GROUP BY d.id_disciplina, d.nome_disciplina, d.semestre
ORDER BY profundidade_maxima DESC, total_prereqs_transitivos DESC;
Displaying records 1 - 10
disciplina semestre_curriculo total_prereqs_transitivos profundidade_maxima
Projeto Aplicado 8 - Sistema em Tempo Real 8 6 3
Monografia 8 5 3
Bases da Eng. de Software 8 8 5 3
Tecnologia Educacional - Design 8 3 3
Bases da Eng. de Software 6 6 4 2
Projeto Aplicado 6 - Machine Learning 6 2 2
Eletiva II 6 2 2
Economia Brasileira 6 2 2
Orçamento e Finanças Públicas 6 1 1
Projeto Aplicado 4 - blockchain 4 1 1

Exemplo 3 — Hierarquia de Estrutura Acadêmica

A estrutura Centro → Escola → Curso → Disciplina é uma hierarquia. Embora tenhamos JOINs diretos para ela, o padrão WITH RECURSIVE funciona igualmente para qualquer árvore onde a relação pai–filho é armazenada em tabela:

-- Hierarquia completa: centro → escola → curso (sem recursão, mas ilustra o padrão)
WITH estrutura AS (
    SELECT ce.nome_centro  AS nivel1,
           es.nome_escola  AS nivel2,
           cu.nome_curso   AS nivel3,
           cu.id_curso
    FROM   centro  ce
    JOIN   escola  es ON es.id_centro = ce.id_centro
    JOIN   curso   cu ON cu.id_escola = es.id_escola
)
SELECT e.nivel1, e.nivel2, e.nivel3,
       COUNT(a.id_aluno) AS alunos
FROM   estrutura e
LEFT JOIN aluno a ON a.id_curso = e.id_curso
GROUP BY e.nivel1, e.nivel2, e.nivel3
ORDER BY e.nivel1, e.nivel2, e.nivel3;
3 records
nivel1 nivel2 nivel3 alunos
Centro de Educação, Magistério e Artes Escola de Educação, Magistério e Arte Pedagogia 6
Centro de Engenharias, Tecnologia e Inovação Escola Superior de Engenharias, Tecnologia e Inovação Engenharia de Software 6
Ciências Humanas, Cidadania e Meio Ambiente Escola Superior de Gestão Ciências Econômicas 6

Guardas Contra Recursão Infinita

Aviso

Se o grafo contiver ciclos (A → B → A), a CTE recursiva pode não terminar. Estratégias de proteção:

  1. UNION em vez de UNION ALL: elimina duplicatas entre iterações — se um nó já foi visitado, não é reinserido na próxima iteração.
  2. Contador de profundidade com WHERE profundidade < N: limita o número de iterações.
  3. Array de caminho: acumula os nós visitados e verifica se o próximo já está no array (PostgreSQL específico).

No banco da UnDF, prereq não deveria ter ciclos (uma disciplina não pode ser pré-requisito de si mesma transitivamente), mas em dados reais essa verificação é importante.

-- Exemplo de guarda com profundidade máxima
WITH RECURSIVE prereqs_limitados(id_raiz, id_prereq, profundidade) AS (
    SELECT id_disciplina, id_prereq, 1 FROM prereq
    UNION
    SELECT pt.id_raiz, p.id_prereq, pt.profundidade + 1
    FROM   prereqs_limitados pt
    JOIN   prereq p ON p.id_disciplina = pt.id_prereq
    WHERE  pt.profundidade < 10   -- guarda: no máximo 10 níveis
)
SELECT ...

Para Praticar

-- Disciplinas sem nenhum pré-requisito (pontos de entrada do grafo)
SELECT d.id_disciplina, d.nome_disciplina, d.semestre
FROM   disciplina d
WHERE  d.id_disciplina NOT IN (SELECT id_disciplina FROM prereq)
  AND  d.id_curso = 311
ORDER BY d.semestre;
2 records
id_disciplina nome_disciplina semestre
3110201 Bases da Eng. de Software 2 2
3110202 Projeto Aplicado 2 - site WEB 2 
-- Disciplinas "folha": possuem pré-requisitos mas não são pré-requisito de ninguém
SELECT d.id_disciplina, d.nome_disciplina, d.semestre
FROM   disciplina d
WHERE  d.id_disciplina IN  (SELECT id_disciplina FROM prereq)   -- tem prereq
  AND  d.id_disciplina NOT IN (SELECT id_prereq   FROM prereq)   -- não é prereq de ninguém
ORDER BY d.semestre;
4 records
id_disciplina nome_disciplina semestre
1110801 Monografia 8
2110801 Tecnologia Educacional - Design 8
3110801 Bases da Eng. de Software 8 8
3110802 Projeto Aplicado 8 - Sistema em Tempo Real 8 
-- Quantos pré-requisitos transitivos tem cada disciplina de ENS?
WITH RECURSIVE prereqs_transitivos(id_disciplina_raiz, id_prereq) AS (
    SELECT id_disciplina, id_prereq FROM prereq
    UNION
    SELECT pt.id_disciplina_raiz, p.id_prereq
    FROM   prereqs_transitivos pt
    JOIN   prereq p ON p.id_disciplina = pt.id_prereq
)
SELECT d.nome_disciplina,
       d.semestre,
       COALESCE(COUNT(DISTINCT pt.id_prereq), 0) AS total_prereqs_transitivos
FROM   disciplina d
LEFT JOIN prereqs_transitivos pt ON pt.id_disciplina_raiz = d.id_disciplina
WHERE  d.id_curso = 311
GROUP BY d.id_disciplina, d.nome_disciplina, d.semestre
ORDER BY total_prereqs_transitivos DESC, d.semestre;
8 records
nome_disciplina semestre total_prereqs_transitivos
Projeto Aplicado 8 - Sistema em Tempo Real 8 6
Bases da Eng. de Software 8 8 5
Bases da Eng. de Software 6 6 4
Projeto Aplicado 6 - Machine Learning 6 2
Projeto Aplicado 4 - blockchain 4 1
Bases da Eng. de Software 4 4 1
Bases da Eng. de Software 2 2 0
Projeto Aplicado 2 - site WEB 2 0