Exemplos de CTE Recursiva: Tarefas Práticas

Lição 6.6 · Tempo de leitura: ~9 min · Tarefas para praticar ↓

As CTEs recursivas servem para mais do que organogramas. Nesta lição, você vai aplicar WITH RECURSIVE a quatro tarefas comuns: gerar uma série de datas para preencher lacunas num relatório diário, totalizar vendas em todos os níveis de uma árvore de categorias, explodir uma lista de materiais na lista completa de peças e encontrar todas as rotas entre duas cidades numa rede de estradas com ciclos.

Na lição anterior, você aprendeu como funciona uma CTE recursiva: o membro âncora devolve as linhas iniciais, o membro recursivo encontra o nível seguinte, e a recursão para quando não surge nada de novo. Aqui o mesmo padrão torna-se uma ferramenta para problemas do dia a dia. Cada exemplo mostra uma técnica reutilizável: uma sequência gerada, pares ancestral–descendente, quantidades multiplicadas e um caminho com verificação de ciclos.

O primeiro exemplo é executado no banco de exemplo Sakila. Os outros criam as suas próprias tabelas, por isso execute-os no playground num banco sem dados de exemplo. A sintaxe é a do MySQL 8.0; também funciona no MariaDB 10.2+.

1. Gerar uma Série de Datas para Preencher Lacunas

Um relatório "aluguéis por dia" construído com GROUP BY mostra apenas os dias em que houve aluguéis. Os dias sem aluguéis simplesmente desaparecem, e um gráfico feito com esses dados esconde a lacuna. A solução é gerar um calendário com todos os dias e juntar os dados a ele.

Uma CTE recursiva gera o calendário: a âncora devolve o primeiro dia e cada iteração acrescenta um dia até ao último:

WITH RECURSIVE calendar AS (
    SELECT DATE('2005-05-28') AS day
    UNION ALL
    SELECT day + INTERVAL 1 DAY
    FROM calendar
    WHERE day < '2005-06-16'
)
SELECT c.day, COUNT(r.rental_id) AS rentals
FROM calendar AS c
LEFT JOIN rental AS r
    ON r.rental_date >= c.day
   AND r.rental_date < c.day + INTERVAL 1 DAY
GROUP BY c.day
ORDER BY c.day;

Resultado: 20 linhas, uma para cada dia de 28 de maio a 16 de junho de 2005. De 1 a 13 de junho não há aluguéis, e esses dias mostram 0 em vez de desaparecerem.

Três detalhes importam:

• O LEFT JOIN mantém os dias sem aluguéis; COUNT(r.rental_id) conta apenas os aluguéis reais, por isso os dias vazios ficam com 0.
• A junção usa um intervalo (>= day e < day + 1 dia) em vez de DATE(r.rental_date) = c.day, para que um índice em rental_date continue a poder ser usado.
• O mesmo padrão gera qualquer sequência: números, horas, meses. Uma série com mais de 1000 passos exige aumentar cte_max_recursion_depth.

2. Totais para uma Subárvore Inteira

Numa árvore de categorias, as vendas são registadas em categorias específicas, mas um relatório precisa dos totais de cada ramo: "Computers" tem de incluir portáteis e computadores de secretária, e "Electronics" tem de incluir tudo.

CREATE TABLE product_category (
    category_id INT PRIMARY KEY,
    parent_id INT,
    name VARCHAR(50) NOT NULL
);

INSERT INTO product_category VALUES
    (1, NULL, 'Electronics'),
    (2, 1, 'Computers'),
    (3, 1, 'Phones'),
    (4, 2, 'Laptops'),
    (5, 2, 'Desktops'),
    (6, 3, 'Smartphones');

CREATE TABLE sale (
    sale_id INT PRIMARY KEY,
    category_id INT NOT NULL,
    amount DECIMAL(10, 2) NOT NULL
);

INSERT INTO sale VALUES
    (1, 4, 1200), (2, 4, 800), (3, 5, 700),
    (4, 6, 500), (5, 6, 300), (6, 3, 150);

O truque é construir primeiro todos os pares ancestral–descendente. A âncora emparelha cada categoria consigo mesma; cada iteração acrescenta os filhos dos descendentes já encontrados:

WITH RECURSIVE subtree AS (
    SELECT category_id AS ancestor_id, category_id
    FROM product_category

    UNION ALL

    SELECT s.ancestor_id, c.category_id
    FROM subtree AS s
    INNER JOIN product_category AS c ON c.parent_id = s.category_id
)
SELECT a.name, SUM(sl.amount) AS total_sales
FROM subtree AS s
INNER JOIN product_category AS a ON a.category_id = s.ancestor_id
LEFT JOIN sale AS sl ON sl.category_id = s.category_id
GROUP BY a.category_id, a.name
ORDER BY a.category_id;

Resultado: Electronics 3650.00, Computers 2700.00, Phones 950.00, Laptops 2000.00, Desktops 700.00, Smartphones 800.00.

Cada venda é contada uma vez para a sua própria categoria e uma vez para cada ancestral. "Phones" fica com 950: 150 vendidos diretamente nesta categoria mais 800 de "Smartphones". A agregação acontece na consulta final, porque o MySQL não permite GROUP BY nem funções de agregação no membro recursivo.

3. Explodir uma Lista de Materiais

Uma lista de materiais (BOM, bill of materials) descreve de que é feito um produto. Os componentes têm os seus próprios componentes, e a mesma peça pode aparecer em vários ramos. Para encomendar as peças de uma bicicleta, você precisa da quantidade total de cada peça:

CREATE TABLE part (
    part_id INT PRIMARY KEY,
    part_name VARCHAR(50) NOT NULL
);

INSERT INTO part VALUES
    (1, 'Bicycle'), (2, 'Frame'), (3, 'Wheel'),
    (4, 'Rim'), (5, 'Spoke'), (6, 'Bolt');

CREATE TABLE bom (
    parent_part_id INT,
    child_part_id INT,
    quantity INT NOT NULL,
    PRIMARY KEY (parent_part_id, child_part_id)
);

INSERT INTO bom VALUES
    (1, 2, 1),   -- uma bicicleta tem 1 quadro
    (1, 3, 2),   -- e 2 rodas
    (2, 6, 4),   -- um quadro tem 4 parafusos
    (3, 4, 1),   -- uma roda tem 1 aro
    (3, 5, 36),  -- 36 raios
    (3, 6, 2);   -- e 2 parafusos

Em cada nível, a quantidade de um componente é multiplicada pela quantidade do seu pai:

WITH RECURSIVE explosion AS (
    SELECT child_part_id AS part_id, quantity
    FROM bom
    WHERE parent_part_id = 1

    UNION ALL

    SELECT b.child_part_id, e.quantity * b.quantity
    FROM explosion AS e
    INNER JOIN bom AS b ON b.parent_part_id = e.part_id
)
SELECT p.part_name, SUM(e.quantity) AS total_quantity
FROM explosion AS e
INNER JOIN part AS p ON p.part_id = e.part_id
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

Resultado: Frame 1, Wheel 2, Rim 2, Spoke 72, Bolt 8.

Raios: 2 rodas × 36 = 72. Os parafusos vêm de dois ramos: 4 no quadro e 2 × 2 = 4 nas rodas, e o SUM soma-os em 8. Para obter só as peças compradas, e não as montadas, mantenha as linhas cuja peça não tem componentes próprios: acrescente WHERE NOT EXISTS (SELECT 1 FROM bom AS c WHERE c.parent_part_id = e.part_id).

4. Rotas num Grafo com Ciclos

Uma árvore tem um único caminho até cada nó. Uma rede de estradas é um grafo: as estradas vão nos dois sentidos e formam ciclos, por isso uma recursão ingénua andaria em círculos para sempre. Vamos encontrar todas as rotas de Berlim a Viena:

CREATE TABLE road (
    from_city VARCHAR(30),
    to_city VARCHAR(30),
    distance_km INT NOT NULL,
    PRIMARY KEY (from_city, to_city)
);

INSERT INTO road VALUES
    ('Berlin', 'Prague', 350),
    ('Berlin', 'Leipzig', 190),
    ('Leipzig', 'Prague', 250),
    ('Prague', 'Vienna', 330),
    ('Leipzig', 'Munich', 430),
    ('Munich', 'Vienna', 400);

Cada estrada é guardada uma vez, por isso uma CTE normal edge acrescenta primeiro o sentido inverso. A CTE recursiva trip prolonga cada rota com mais uma estrada, salta as cidades que já estão na rota e deixa de prolongar uma rota quando ela chega a Viena:

WITH RECURSIVE edge AS (
    SELECT from_city, to_city, distance_km FROM road
    UNION ALL
    SELECT to_city, from_city, distance_km FROM road
),
trip AS (
    SELECT
        to_city AS city,
        CAST(CONCAT(from_city, ',', to_city) AS CHAR(500)) AS route,
        distance_km AS total_km
    FROM edge
    WHERE from_city = 'Berlin'

    UNION ALL

    SELECT e.to_city, CONCAT(t.route, ',', e.to_city), t.total_km + e.distance_km
    FROM trip AS t
    INNER JOIN edge AS e ON e.from_city = t.city
    WHERE FIND_IN_SET(e.to_city, t.route) = 0
      AND t.city <> 'Vienna'
)
SELECT route, total_km
FROM trip
WHERE city = 'Vienna'
ORDER BY total_km;

Resultado: 4 rotas; a mais curta é Berlim, Praga, Viena, com 680 km.

FIND_IN_SET(e.to_city, t.route) = 0 é a verificação de ciclos da lição anterior: uma rota nunca volta a uma cidade já visitada. Repare que WITH RECURSIVE se escreve uma vez, e as CTEs que vêm a seguir podem ser normais ou recursivas.

Esta consulta lista todas as rotas possíveis, e o seu número cresce muito depressa com o tamanho da rede. Serve para grafos pequenos, mas em grandes redes de estradas os caminhos mais curtos encontram-se com algoritmos especializados, por exemplo em bancos de dados de grafos ou na extensão do PostgreSQL pgRouting.

Quando uma CTE Recursiva Não É a Melhor Ferramenta

• Árvores profundas lidas com frequência. Se uma hierarquia é lida muito mais vezes do que muda, guarde estrutura extra: um caminho materializado (/1/2/4/) ou uma tabela de fecho (closure table) com todos os pares ancestral–descendente, como a CTE subtree acima, guardada numa tabela. Assim uma subárvore é um simples JOIN sem recursão.
• Grafos grandes. Enumerar rotas é exponencial; use algoritmos de grafos.
• Um número pequeno e fixo de níveis. Para "funcionário e o seu gestor", um único self-join (Lição 5.7) é mais simples.

Principais conclusões:

• Uma CTE recursiva gera sequências: um calendário de datas juntado com LEFT JOIN preenche lacunas nos relatórios.
• Os pares ancestral–descendente construídos por uma CTE recursiva permitem totalizar valores sobre toda uma subárvore.
• Numa lista de materiais, as quantidades são multiplicadas nível a nível e somadas com GROUP BY na consulta final.
• Em grafos com ciclos, guarde os nós visitados num caminho e salte-os com FIND_IN_SET().
• A agregação pertence à consulta final: o MySQL não a permite no membro recursivo.
• Para grafos grandes ou árvores lidas com muita frequência, considere tabelas de fecho ou algoritmos de grafos.

Perguntas Frequentes

Como gerar uma série de datas no MySQL?

Use uma CTE recursiva: WITH RECURSIVE calendar AS (SELECT DATE('2024-01-01') AS day UNION ALL SELECT day + INTERVAL 1 DAY FROM calendar WHERE day < '2024-01-31') SELECT day FROM calendar;. O PostgreSQL também tem a função integrada generate_series().

Como preencher datas em falta num relatório SQL?

Gere com uma CTE recursiva um calendário de todas as datas, depois junte-lhe os dados com LEFT JOIN e conte uma coluna da tabela juntada, como COUNT(r.rental_id). As datas sem dados ficam com 0 em vez de desaparecerem.

Como calcular um total para um nó e todos os seus descendentes?

Construa os pares ancestral–descendente com uma CTE recursiva: a âncora emparelha cada nó consigo mesmo, e o membro recursivo acrescenta os filhos de cada descendente. Depois junte os valores aos descendentes e agrupe pelo ancestral com GROUP BY.

Como evitar ciclos ao percorrer um grafo com uma CTE recursiva?

Guarde o caminho dos nós visitados numa coluna de texto e acrescente ao membro recursivo uma condição como FIND_IN_SET(next_node, path) = 0. O PostgreSQL 14+ também tem uma cláusula CYCLE que marca e para os ciclos automaticamente.