Рекурсивный CTE и цикл в иерархии: как не уйти в бесконечный обход

В справочнике подразделений по ошибке появилась связь обратно к предку. Запрос обхода дерева теперь повторяет одни и те же вершины. Прежде чем строить отчёт по иерархии, нужно решить, как обнаруживать цикл и ограничивать повреждённый путь.

Как разобрать ситуацию

Для небольшого учебного графа переносим строковый путь с разделителями. Перед переходом проверяем, встречался ли следующий id именно как целая вершина. Разделители важны: без них идентификатор 1 ошибочно совпадёт с 11. Дополнительно ограничим глубину, чтобы повреждённые данные не раздували вычисление.

Пример и ожидаемый результат

Есть связи 1→2, 2→3 и 3→1. Обход от 1 должен вернуть пути к 1, 2 и 3, после чего остановиться. Повторное посещение 1 не является новым элементом дерева.

WITH RECURSIVE edges(a,b) AS(VALUES(1,2),(2,3),(3,1)), walk(id,path,depth) AS(
SELECT 1,',1,',0 
UNION ALL 
SELECT e.b,w.path||e.b||',',w.depth+1 
FROM walk w 
JOIN edges e ON e.a=w.id 
WHERE instr(w.path,','||e.b||',')=0 AND w.depth<10) 
SELECT id 
FROM walk 
ORDER BY depth;

Запрос возвращает узлы 1, 2 и 3 по одному разу для выбранного пути. Циклическое ребро не расширяет рекурсию.

Проверка перед применением

• Добавьте соседнюю вершину 11 и проверьте, что проверка не путает её с 1.
• Протестируйте прямую петлю 1→1.
• Отдельно сохраните сигнал о найденном цикле: молчаливое исключение ребра не исправляет справочник.

Договоритесь с владельцем данных о поведении отчёта при повреждении: остановить публикацию, показать неполный результат с предупреждением или отправить запись на разбор. Просто увеличить лимит глубины опасно: это откладывает симптом и не делает циклическую структуру корректным деревом.

Границы решения

Строковый путь не является универсальным оптимальным представлением графа. Для больших графов и сложных ключей нужны другие структуры. Здесь использованы целочисленные id и синтаксис SQLite.

Если запросы уже пишутся, а уверенности в кардинальности, оконных рамках и проверке результата не хватает, продолжить практику можно в нашем платном курсе

Продвинутый SQL: сложные запросы и задачи для собеседований. Перед записью сравните программу со своей задачей и подготовкой.

Техническая справка: www.sqlite.org: документация.

Следующий шаг: Сложные SQL-запросы: разборы расчётов и ошибок. По смежным вопросам: Фильтр дат SQL: как включить весь месяц и не захватить следующий, Как разбить события на сессии в SQL по паузе между действиями.