Consultas recursivas (WITH RECURSIVE): jerarquías y grafos

Recorre árboles y grafos con WITH RECURSIVE, dominando la profundidad y la detección de ciclos.

11 min · 3 preguntas

Una CTE recursiva se compone de dos partes unidas por UNION ALL: un término de anclaje que proporciona las filas iniciales, y un término recursivo que hace referencia a la propia CTE. SQLite ejecuta el anclaje una vez, luego aplica el término recursivo en bucle sobre las filas nuevas, hasta que no produce ninguna. Creemos una jerarquía de responsables para ilustrarlo.

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

Para desplegar el organigrama bajo Ada, el anclaje selecciona la raíz con una profundidad de 0, y el término recursivo une cada empleado a su responsable ya presente en la CTE, incrementando la profundidad. La columna depth que calculas tú mismo es la forma más sencilla de medir los niveles de una jerarquía.

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

Un grafo se modela mediante una tabla de aristas (src, dst). El recorrido sigue la misma mecánica, pero un grafo puede contener ciclos: seguir 1 -> 2 -> 3 -> 1 da vueltas para siempre. El remedio es recordar el camino recorrido en una columna de texto y rechazar todo nodo ya visitado. La función instr busca un nodo entre dos puntos dentro de ese camino.

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

Prueba de conocimientos

Comprueba que has retenido los puntos clave de esta lección.

1. En una CTE recursiva, ¿qué operador une el término de anclaje con el término recursivo?
   • UNION ALL (o UNION)
   • JOIN
   • INTERSECT
   • CROSS APPLY
2. ¿Por qué un grafo cíclico corre el riesgo de recursión infinita con UNION ALL?
   • Porque UNION ALL ordena sistemáticamente los resultados
   • Porque los mismos nodos se revisitan sin deduplicación
   • Porque SQLite desactiva el índice durante la recursión
   • Porque el anclaje se reevalúa en cada pasada
3. ¿Cómo se evita un bucle infinito al recorrer un grafo cíclico en SQLite?
   • Añadir un ORDER BY en el término recursivo
   • Recordar el camino recorrido y excluir los nodos ya visitados
   • Usar la cláusula estándar CYCLE
   • Aumentar el tamaño de la caché de memoria