Conozca el poder de las consultas recursivas de SQL

Lo más habitual es que las consultas SQL que ejecutamos en una base de datos sean bastante sencillas. Bueno, eso depende de su función, por supuesto. Los analistas de los almacenes de datos recuperan tipos de información completamente diferentes utilizando (muy a menudo) consultas mucho más complicadas que los ingenieros de software que crean aplicaciones CRUD.

Sin embargo, a veces es más sencillo o elegante ejecutar una consulta un poco más sofisticada sin necesidad de procesar más datos en el código. Una forma de conseguirlo es con una función de SQL llamada consultas recursivas.

Tomemos un ejemplo de la vida real. Supongamos que tenemos una base de datos con una lista de nodos y una lista de enlaces entre ellos (puedes pensar en ellos como ciudades y carreteras). Nuestra tarea es encontrar el camino más corto desde el nodo 1 al nodo 6.

De hecho, no es más que un recorrido del grafo. La primera idea que podría tener un ingeniero de software medio sería obtener todas las filas de ambas tablas e implementar un algoritmo DFS (Depth-First Search) o BFS (Breadth-First Search) en su lenguaje de programación favorito. ¡No es una mala idea (si te gusta la codificación 😉 ) pero puedes hacerlo con una sola consulta SQL!

Cláusula WITH - ¡Expresiones de tabla comunes al rescate!

Nota: todos los ejemplos están escritos para PostgreSQL 9.3; sin embargo, no debería ser difícil hacerlos utilizables con un RDBMS diferente.

Si su RDBMS es PostgreSQL, IBM DB2, MS SQL Server, Oracle (sólo a partir de la versión 2 de 11g), o MySQL (sólo a partir de la versión 8.0.1) puede utilizar consultas WITH, conocidas como Expresiones de Tabla Comunes (CTEs). En general, permiten dividir las consultas complicadas en un conjunto de consultas más sencillas que facilitan la lectura de la consulta. La estructura de una cláusula WITH es la siguiente:

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

Por ejemplo, podemos querer obtener como máximo 3 nodos, cuya longitud total de enlaces salientes sea al menos 100 y al menos un enlace saliente tenga una longitud superior a 50. No hace falta que entiendas del todo el siguiente ejemplo, basta con que te fijes en la estructura de la consulta. En lugar de escribir una 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 escribirla así:

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);

Las consultas se definen por separado, lo que facilita mucho la comprensión a la hora de implementar ejemplos mucho más complicados.

Un punto importante: Los CTEs también pueden tener una estructura recursiva:

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

¿Cómo funciona?

Es muy sencillo. En el primer paso se evalúa un término no recursivo. A continuación, por cada fila de resultados de la evaluación anterior, se evalúa un término recursivo y sus resultados se añaden a los anteriores. El término recursivo tiene acceso a los resultados del término previamente evaluado.

Un ejemplo sencillo #1

Veamos un ejemplo sencillo: la multiplicación 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)

En el primer paso, la única fila de resultados es "1". Entonces, hay UNION ALL con un término recursivo. 1 se multiplica por 2, lo que da lugar a una fila de resultados: "2". Por ahora, hay dos filas de resultados: 1, 2. Sin embargo, la última evaluación del término produjo sólo una fila - "2" - y se pasará al siguiente paso recursivo. 2 se multiplica por 2, lo que devuelve "4", y así sucesivamente... En este ejemplo, la recursión sería infinita si no especificáramos la cláusula LIMIT.

Un ejemplo fácil #2

Hagamos otro ejemplo rápido (típicamente académico): la secuencia de Fibonacci. Se define como sigue:

Una función de este tipo se puede definir en SQL utilizando la 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 el concepto esté ahora claro.

Recorrido del gráfico

Volvamos a nuestro ejemplo con el recorrido de un gráfico. Lo que queremos hacer es encontrar el camino más corto entre dos nodos. Así es como se ve la estructura de la DB:

Para que nuestro SQL sea más legible, vamos a definir una vista simple node_links_view uniendo node con link y con node de nuevo:

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);

Ahora, la estructura de nuestro modelo tiene el siguiente aspecto:

¿Qué necesitamos como resultado de la consulta? Queremos un camino exacto entre los nodos y su longitud completa. Para excluir cualquier ciclo en el gráfico, también necesitamos una bandera para identificar si el último nodo ya fue visitado. Por lo tanto, la primera parte de la definición del CTE tendrá este aspecto:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 

En el primer paso tenemos que obtener todos los enlaces desde el nodo inicial:

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

Es nuestro término no recursivo.

Ahora, iremos recursivamente empezando por el último nodo visitado, que es el último elemento de un array:

    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;

¿Cómo funciona? Mira las cláusulas FROM y WHERE. La consulta obtiene las siguientes filas de node_link_view que comienzan en el último nodo de la evaluación anterior que no terminó con un ciclo. Devuelve un array ampliado con un nodo destino del enlace, una suma de longitudes y una bandera que determina si este nodo fue visitado previamente. Esta parte recursiva de la consulta se ejecutará siempre que haya algún enlace con nodos no visitados.

Así pues, aquí tenemos una consulta SQL completa que recupera todas las rutas desde el nodo con id=1 hasta el nodo con 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 obtenemos todos los caminos desde el nodo 1 hasta el nodo 6 ordenados por la longitud total del camino:

   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) 

El camino más corto es el primero, por lo que podríamos añadir una cláusula LIMIT para obtener un solo resultado.

¿Recuerdas que creamos la vista externa - node_links_view - para facilitar la lectura del SQL? Podemos hacer lo mismo con una 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 ejemplo no está en absoluto optimizado! Su propósito es sólo mostrarle cómo usar CTEs recursivos.

Oracle (Antes de la versión 2 de 11g) - Consultas Jerárquicas

Hasta la versión 2 de Oracle 11g, las bases de datos Oracle no soportaban consultas recursivas WITH. En Oracle SQL este tipo de consultas se denominan consultas jerárquicas y tienen una sintaxis completamente diferente, pero la idea es la misma. Puede leer más sobre las consultas jerárquicas en la documentación de Oracle.

MySQL - 33 meses de silencio...

Malas noticias para los usuarios de MySQL. No soporta la cláusula WITH a pesar de que hubo muchas peticiones de características pidiéndolo. Probablemente la primera fue esta, que ha sido ignorada durante 33 meses y no ha sido resuelta desde enero de 2006...

Actualización: Las consultas recursivas WITH están disponibles en MySQL desde la versión 8.0.1, publicada en abril de 2017.

Espero que la idea de las consultas recursivas te quede clara ahora. ¡Disfruta de las consultas recursivas!