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

У меня есть список смежности в базе данных с идентификатором и 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

Теперь мой вопрос: при вставке/обновлении есть ли способ проверить, произойдет ли циклическая ссылка?

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


mysql sql adjacency-list circular-reference
person Dylan    schedule 20.02.2011    source источник
comment
На данный момент я решил это, отслеживая используемые идентификаторы в рекурсивном цикле пути. Когда он видит идентификатор, который уже использовался, он вставляет «NULL» вместо идентификатора. Может быть, не очень элегантно, но, похоже, работает...   -  person Dylan    schedule 20.02.2011

Ответы (2)


arrow_upward
1
arrow_downward

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

person dj_segfault    schedule 20.02.2011
comment
Это то, что я понял, сначала я хранил используемые идентификаторы в отдельном массиве, но при построении пути я мог просто использовать саму строку пути для проверки идентификатора :) - person Dylan; 20.02.2011

arrow_upward
0
arrow_downward

Если вы используете 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

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

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

person bdeem    schedule 16.04.2013