В иерархии категорий внешний ключ запрещает отсутствующего родителя, но допускает цикл из нескольких категорий. Какая дополнительная гарантия нужна, чтобы сохранить ацикличность?
Нужна гарантия ацикличности графа: при добавлении или изменении родителя новая связь не должна делать категорию своим собственным предком через цепочку из нескольких строк. Обычный внешний ключ проверяет только существование непосредственного родителя и не анализирует транзитивные связи.
Для надёжного контроля используют проверку при изменении данных: триггер или хранимую процедуру с рекурсивным обходом и блокировками. В системах с интенсивными запросами к иерархии также применяют таблицу транзитивного замыкания, но её согласованность всё равно должна поддерживаться атомарно.
Простейшая модель дерева хранит у каждой категории идентификатор непосредственного родителя. Такая модель называется списком смежности. Она компактна, естественно выражает связь внешним ключом и удобна для изменения одного узла.
Внешний ключ решает исходную проблему ссылочной целостности: нельзя указать родителя, которого нет. Однако реляционные ограничения на уровне отдельных строк не всегда выражают свойства всего графа. Ацикличность относится именно к свойству множества строк и цепочек связей, а не одной строки.
Пусть категория A ссылается на B, B — на C, а C — обратно на A. Каждая ссылка по отдельности корректна: все указанные родители существуют. Но вместе строки образуют цикл, поэтому ни одна категория не является корнем и обход дерева никогда не завершится.
Особый случай — ссылка категории на саму себя. Её можно запретить проверкой неравенства идентификаторов, но это не решает проблему циклов длиной два и более. Например, запрет самоссылки не помешает A ссылаться на B, а B — на A.
Ошибки проявляются в рекурсивных запросах, построении меню, расчёте уровня вложенности и удалении поддеревьев. В зависимости от СУБД и запроса результатом могут стать повторяющиеся узлы, ограничение глубины рекурсии, ошибка выполнения или бесконечная логическая обработка.
При изменении категории нужно проверить, что новый родитель не находится внутри поддерева этой категории. Иначе после добавления связи путь от нового родителя вверх когда-нибудь вернётся к изменяемой категории, то есть возникнет цикл.
Для списка смежности обычно применяют следующий алгоритм:
Обычный CHECK для этого не подходит: он предназначен прежде всего для проверки значения текущей строки и не выражает надёжное транзитивное условие по произвольному числу строк. Внешний ключ также не подходит, потому что проверяет наличие конкретного значения в целевой таблице, но не отсутствие пути обратно.
Триггер или единая хранимая процедура позволяют автоматически проверять все изменения, включая операции, выполненные разными приложениями. Но рекурсивная проверка должна учитывать конкурентные транзакции. Иначе две параллельные операции могут пройти проверки на ещё не зафиксированных данных, а после фиксации вместе создать цикл. Нужны подходящие блокировки, сериализация изменений дерева или другой механизм согласования.
Таблица транзитивного замыкания хранит не только непосредственных родителей, но и все пары предок — потомок. Тогда попытку добавить связь можно проверять через наличие обратной пары. Такой подход ускоряет чтение всех предков и потомков, но усложняет запись: при перемещении поддерева нужно корректно обновить множество транзитивных связей. Обычно это делают через одну транзакцию и ограниченный интерфейс изменения иерархии.
Дополнительные внешние ключи и ограничение, запрещающее равенство предка и потомка, полезны, но сами по себе недостаточны. Они защищают локальные случаи, тогда как полная гарантия требует проверки всей цепочки.
В каталоге интернет-магазина категории изначально хранились как список смежности. Приложение проверяло, что новая категория не становится своим потомком, но один административный сценарий обновлял родителя напрямую. В результате две параллельные операции переместили узлы в разные ветви и создали цикл из нескольких категорий.
Рассматривались три варианта. Проверка только в приложении была простой и быстрой, но не защищала от других клиентов и гонок. Таблица транзитивного замыкания ускоряла построение полного пути и упрощала чтение, но значительно усложняла перемещение поддеревьев. Триггер с рекурсивной проверкой сохранил компактную модель и централизовал правило, однако потребовал блокировать изменения структуры дерева.
Выбрали единый серверный метод изменения родителя, триггерную проверку и блокировку строк затронутой ветви. Внешний ключ оставили для проверки существования родителя, а отдельное условие запретило непосредственную самоссылку. В результате все каналы изменения стали проходить одну проверку, а операции перемещения выполнялись последовательно и предсказуемо.
1. Достаточно ли запретить ссылку категории на саму себя?
Нет. Это устраняет только цикл длиной один. Цикл длиной два возникает, когда A указывает на B, а B — на A; более длинные циклы строятся аналогично. Поэтому проверка должна искать изменяемую категорию во всей цепочке предков нового родителя.
2. Почему внешнего ключа недостаточно, если все родительские строки существуют?
Внешний ключ проверяет локальное условие: значение parent_id должно соответствовать существующей строке родителя либо допустимому отсутствующему значению. Он не проверяет достижимость через несколько переходов и не вычисляет, вернётся ли путь к исходной категории. Поэтому ссылочная целостность и ацикличность — разные свойства модели.
3. Может ли корректный рекурсивный триггер гарантировать ацикличность при параллельных изменениях?
Не обязательно. Если два изменения выполняются одновременно и каждое читает неполное состояние дерева, отдельные проверки могут пройти, хотя объединённый результат будет циклическим. Для гарантии нужны сериализация структурных изменений, блокировки, подходящий уровень изоляции или централизованная процедура, которая атомарно проверяет и изменяет граф.