Рекурсивные запросы (WITH RECURSIVE): иерархии и графы

Обходи деревья и графы с помощью WITH RECURSIVE, управляя глубиной и обнаружением циклов.

11 мин · 3 вопросов

Рекурсивный CTE состоит из двух частей, соединённых через UNION ALL: якорная часть даёт начальные строки, а рекурсивная часть ссылается на сам CTE. SQLite один раз выполняет якорь, затем в цикле применяет рекурсивную часть к новым строкам, пока она не перестанет их выдавать. Создадим иерархию руководителей, чтобы это показать.

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

Чтобы развернуть оргструктуру под Ada, якорь выбирает корень с глубиной 0, а рекурсивная часть присоединяет каждого сотрудника к его руководителю, уже присутствующему в CTE, увеличивая глубину. Столбец depth, который ты считаешь сам, - самый простой способ измерить уровни иерархии.

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;

Граф моделируется таблицей рёбер (src, dst). Обход работает по той же механике, но в графе бывают циклы: путь 1 -> 2 -> 3 -> 1 будет крутиться вечно. Лекарство - запоминать пройденный путь в текстовом столбце и отбрасывать любую уже посещённую вершину. Функция instr ищет вершину между двумя точками внутри этого пути.

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;

Проверка знаний

Убедись, что запомнил ключевые моменты этого урока.

1. Какой оператор связывает якорную часть с рекурсивной в рекурсивном CTE?
   • UNION ALL (или UNION)
   • JOIN
   • INTERSECT
   • CROSS APPLY
2. Почему циклический граф рискует уйти в бесконечную рекурсию с UNION ALL?
   • Потому что UNION ALL всегда сортирует результаты
   • Потому что одни и те же вершины посещаются заново без устранения дублей
   • Потому что SQLite отключает индекс во время рекурсии
   • Потому что якорь пересчитывается на каждом проходе
3. Как избежать бесконечного цикла при обходе циклического графа в SQLite?
   • Добавить ORDER BY в рекурсивную часть
   • Запоминать пройденный путь и исключать уже посещённые вершины
   • Использовать стандартную конструкцию CYCLE
   • Увеличить размер кэша памяти