Дерево списка смежности - как предотвратить циклические ссылки?

Question

У меня есть список смежности в базе данных с ID и ParentID для представления древовидной структуры:

-a
--b
---c
-d
--e

Конечно, в записи ParentID никогда не должен совпадать с ID, но я также должен запретить циклические ссылки, чтобы предотвратить бесконечный цикл. Эти циклические ссылки могут в теории включать более двух записей. (a-> b, b-> c, c-> a и т. д.)

Для каждой записи я храню пути в строковом столбце следующим образом:

a    a
b    a/b
c    a/b/c
d    d
e    d/e

Мой вопрос сейчас: при вставке / обновлении есть ли способ проверить наличие круговой ссылки?

Я должен добавить, что я знаю все о модели вложенных множеств и т. Д. Я выбрал метод смежности с сохраненными путями, потому что я считаю его гораздо более интуитивным. Я получил его, работающий с триггерами и отдельной таблицей путей, и он работает как шарм, за исключением возможных циклических ссылок.

Answer 1

Если вы храните путь таким образом, вы можете проверить, что путь не содержит идентификатора.

Answer 2

Если вы используете Oracle, вы можете реализовать проверку циклов, используя синтаксис CONNECT BY.Количество узлов должно быть равно количеству потомков от корневого узла.

CHECK (
(SELECT COUNT(*) Nodes
 FROM Tree) =
(SELECT COUNT(*) Decendents
 FROM Tree
 START WITH parent_node IS NULL -- Root Node
 CONNECT BY parent_node = PRIOR child_node))

Обратите внимание, что вам все равно понадобятся другие проверки для обеспечения соблюдения дерева.IE

Единственный корневой узел с нулевым значением.Узел может иметь ровно одного родителя.

Невозможно создать проверочное ограничение с помощью подзапроса, поэтому для этого потребуется перейти к представлению или триггеру.