Conheça o Poder das Consultas Recursivas SQL

Mais comumente, as consultas SQL que executamos em um banco de dados são bastante simples. Bem, isso depende de seu papel, é claro. Analistas em data warehouses recuperam tipos de informações completamente diferentes usando (muitas vezes) consultas muito mais complicadas do que os engenheiros de software que criam aplicações CRUD.

Entretanto, às vezes é mais simples ou mais elegante executar uma consulta que é um pouco mais sofisticada sem precisar de mais processamento de dados no código. Uma maneira de realizar isto é com um recurso SQL chamado consultas recursivas.

Vamos tomar um exemplo da vida real. Vamos assumir que temos um banco de dados com uma lista de nós e uma lista de links entre eles (você pode pensar neles como cidades e estradas). Nossa tarefa é encontrar o caminho mais curto entre o nó 1 e o nó 6.

Na verdade, nada mais é do que uma travessia gráfica. A primeira idéia que um engenheiro de software médio pode ter seria obter todas as linhas de ambas as tabelas e implementar um algoritmo DFS (Depth-First Search) ou BFS (Breadth-First Search) em sua linguagem de programação favorita. Não é uma má idéia (se você gosta de codificar 😉 ) mas você pode fazer isso com uma única consulta SQL!

COM Cláusula - Expressões comuns da tabela para o Rescue!

Nota: todos os exemplos são escritos para o PostgreSQL 9.3; entretanto, não deve ser difícil torná-los utilizáveis com um RDBMS diferente.

Se seu RDBMS é PostgreSQL, IBM DB2, MS SQL Server, Oracle (somente a partir da versão 2 de 11g), ou MySQL (somente a partir da versão 8.0.1) você pode usar COM consultas, conhecidas como Expressões Comuns de Tabelas (CTEs). De modo geral, elas permitem dividir as consultas complicadas em um conjunto de consultas mais simples, o que torna uma consulta mais fácil de ler. A estrutura de uma cláusula COM AQUI é a seguinte:

WITH [cte_name] AS (
	[cte_term])
SELECT ... FROM [cte_name];

Por exemplo, podemos querer obter no máximo 3 nós, cujo comprimento total de links de saída é de pelo menos 100 e pelo menos um único link de saída tem um comprimento maior que 50. Você não precisa entender completamente o exemplo a seguir, basta olhar para a estrutura da consulta. Ao invés de escrever uma consulta como esta:

SELECT * FROM node 
WHERE id IN (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN (
        SELECT node_from_id
        FROM link 
        GROUP BY node_from_id 
        HAVING SUM(length) >= 100 
        ORDER BY SUM(length) DESC
        LIMIT 3));

podemos escrevê-la desta forma:

WITH
longest_outgoing_links AS (
    SELECT node_from_id
    FROM link 
    GROUP BY node_from_id 
    HAVING SUM(length) >= 100 
    ORDER BY SUM(length) DESC
    LIMIT 3),
nodes_from_longest_outgoing_links AS (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN 
         (SELECT * FROM longest_outgoing_links)
)
SELECT * FROM node 
WHERE id IN (SELECT * FROM nodes_from_longest_outgoing_links);

As consultas são definidas separadamente, o que torna muito mais fácil de entender ao implementar exemplos muito mais complicados.

Um ponto importante: Os CTEs também podem ter uma estrutura recursiva:

WITH RECURSIVE [cte_name] (column, ...) AS (
    [non-recursive_term]
    UNION ALL
    [recursive_term])
SELECT ... FROM [cte_name];

Como funciona?

É bastante simples. No primeiro passo, um termo não recursivo é avaliado. Em seguida, para cada linha de resultado da avaliação anterior, um termo recursivo é avaliado e seus resultados são anexados aos anteriores. O termo recursivo tem acesso aos resultados do termo previamente avaliado.

Um exemplo fácil nº 1

Vejamos um exemplo simples - multiplicação por 2:

WITH RECURSIVE x2 (result) AS ( 
    SELECT 1 
    UNION ALL 
    SELECT result*2 FROM x2) 
SELECT * FROM x2 LIMIT 10; 

 result 
-------- 
      1 
      2 
      4 
      8 
     16 
     32 
     64 
    128 
    256 
    512 
(10 rows)

No primeiro passo, a única linha de resultado é "1". Em seguida, há UNION ALL com um termo recursivo. 1 é multiplicado por 2, o que resulta em uma fileira de resultados - "2". Por enquanto, há duas fileiras de resultados: 1, 2. Entretanto, a última avaliação do termo produziu apenas uma linha - "2" - e ela será passada para a próxima etapa recursiva. 2 é multiplicado por 2, que retorna "4," e assim por diante. Neste exemplo, a recursividade seria infinita se não especificássemos a cláusula LIMIT.

Um exemplo fácil nº 2

Vamos fazer outro exemplo rápido (tipicamente acadêmico) - a seqüência de Fibonacci. Ela é definida da seguinte forma:

Tal função pode ser definida em SQL usando a cláusula WITH:

WITH RECURSIVE fib(f1, f2) AS ( 
    SELECT 0, 1 
    UNION ALL 
    SELECT f2, (f1+f2) FROM fib ) 
SELECT f1 FROM fib LIMIT 10;

 f1 
---- 
  0 
  1 
  1 
  2 
  3 
  5 
  8 
 13 
 21 
 34 
(10 rows)

Espero que o conceito esteja agora claro.

Traversal Gráfico

Voltemos ao nosso exemplo com uma travessia gráfica. O que queremos fazer é encontrar o caminho mais curto entre dois nós. É assim que se parece a estrutura DB:

Só para tornar nosso SQL mais legível, vamos definir uma visão simples node_links_view juntando node com link e com node novamente:

CREATE VIEW node_links_view AS 
SELECT 
    n1.id AS node_id, 
    n1.name AS node_name, 
    n2.id AS destination_node_id, 
    n2.name AS destination_node_name, 
    l.length AS link_length 
FROM 
    node n1 
    JOIN link l ON (n1.id = l.node_from_id) 
    JOIN node n2 ON (l.node_to_id = n2.id);

Agora, nossa estrutura de modelo se parece com a seguinte:

O que precisamos como resultado da consulta? Queremos um caminho exato entre os nós e todo o seu comprimento. A fim de excluir quaisquer ciclos no gráfico, precisamos também de uma bandeira para identificar se o último nó já foi visitado. Portanto, a primeira parte da definição do CTE será parecida com esta:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 

No primeiro passo, temos que obter todos os links desde o nó inicial:

   
SELECT 
    ARRAY[node_id, destination_node_id], 	-- path_ids
    link_length,  				-- length
    node_id = destination_node_id  		-- is_visited
FROM 
    node_links_view;

É nosso termo não-recursivo.

Agora, iremos recursivamente a partir do último nó visitado, que é o último elemento de uma matriz:

    SELECT 
        path_ids || d.destination_node_id,  	-- path_ids
        f.length + d.link_length, 		-- length
        d.destination_node_id = ANY(f.path_ids)	-- is_visited
    FROM 
        node_links_view d, 
        search_path f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited;

Como funciona? Veja as cláusulas FROM e WHERE. A consulta obtém as próximas linhas de node_link_view que começam no último nó da avaliação anterior que não terminou com um ciclo. Ela retorna um array estendido com um nó de destino do link, uma soma de comprimentos e uma bandeira determinando se este nó foi visitado anteriormente. Esta parte recursiva da consulta será executada desde que haja algum link para nós não visitados.

Portanto, aqui está uma consulta SQL completa recuperando todos os caminhos do nó com id=1 para o nó com id=6:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        node_id = destination_node_id 
    FROM 
        node_links_view 

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM 
        node_links_view d, 
        search_path f 
    WHERE 
    f.path_ids[array_length(path_ids, 1)] = d.node_id 
    AND NOT f.is_visited 
) 
SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length;

Como resultado, obtemos todos os caminhos do nó 1 até o nó 6 ordenados pelo comprimento total do caminho:

   path_ids    | length | is_visited 
---------------+--------+------------ 
 {1,3,2,5,6}   |    140 | f 
 {1,2,5,6}     |    150 | f 
 {1,3,4,5,6}   |    150 | f 
 {1,3,4,6}     |    190 | f 
 {1,2,3,4,5,6} |    200 | f 
 {1,2,3,4,6}   |    240 | f 
(6 rows) 

O caminho mais curto é o primeiro, então poderíamos adicionar uma cláusula LIMIT para obter apenas um resultado.

Lembre-se que criamos a visão externa - node_links_view - para tornar o SQL mais fácil de ler? Podemos fazer o mesmo com um CTE:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        node_id = destination_node_id 
    FROM node_links_select

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM node_links_select d, 
        search_path f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited 
), 

node_links_select AS ( 
    SELECT 
        n1.id AS node_id, 
        n1.name AS node_name, 
        n2.id AS destination_node_id, 
        n2.name AS destination_node_name, 
        l.length AS link_length 
    FROM 
        node n1 
        JOIN link l ON (n1.id = l.node_from_id) 
        JOIN node n2 ON (l.node_to_id = n2.id) 
)

SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length;

Nota: este exemplo não é de forma alguma otimizado! Seu objetivo é apenas mostrar como usar CTEs recursivos.

Oracle (Antes do Release 2 de 11g) - Consultas Hierárquicas

Até o Oracle 11g release 2, os bancos de dados Oracle não suportavam consultas recursivas COM consultas. Em Oracle SQL este tipo de consultas são chamadas consultas hierárquicas e têm uma sintaxe completamente diferente, mas a idéia é bem a mesma. Você pode ler mais sobre consultas hierárquicas na documentação do Oracle.

MySQL - 33 Meses de Silêncio...

Más notícias para os usuários do MySQL. Ele não suporta a cláusula com a cláusula, embora houvesse muitos pedidos de recursos pedindo por ela. Provavelmente a primeira foi esta que tinha sido ignorada por 33 meses e não foi resolvida desde janeiro de 2006...

Atualização: Consultas recursivas com o MySQL estão disponíveis desde a versão 8.0.1, publicada em abril de 2017.

Espero que a idéia de consultas recursivas esteja agora clara para você. Aproveite as consultas recursivas recursivas!