Insert into t_Base(Node) values (@NewRoot);
-- Получаем уникальный идентификатор нового элемента
SELECT @RootID=ID FROM T_Base WHERE Node=@NewRoot;
-- Добавляем строку корневого элемента во вспомогательную таблицу
Insert into t_Helper(uid, ParentId, [Level])
Values (@RootId, @RootId, 0);
-- ВНИМАНИЕ! Тут должна быть проверка результатов и,
-- если были ошибки, откат транзакции!
COMMIT TRANSACTION AddNodeTransaction;
END;
Теперь первичное заполнение структуры данных можно реализовать следующей последовательностью вызовов хранимых процедур:
EXEC AddRootNode 'A';
EXEC AddNode 'A', 'B';
EXEC AddNode 'A', 'C';
EXEC AddNode 'B', 'D';
EXEC AddNode 'B', 'E';
EXEC AddNode 'D', 'I';
EXEC AddNode 'E', 'J';
EXEC AddNode 'E', 'K';
EXEC AddNode 'E', 'L';
EXEC AddNode 'C', 'F';
EXEC AddNode 'C', 'G';
EXEC AddNode 'C', 'H';
EXEC AddNode 'F', 'O';
EXEC AddNode 'G', 'M';
EXEC AddNode 'G', 'N';
EXEC AddNode 'H', 'P';
Удаление одиночных узлов и поддеревьев может быть выполнено при помощи триггера. Триггер назначается таблице T_Base на операцию удаления записей. Будем полагать, что при удалении узла удаляются и все его потомки.
CREATE TRIGGER DeleteNode
ON T_Base
Instead of delete
AS
-- Добавляем узлы дерева
-- ВНИМАНИЕ! После каждой операции необходима
-- проверка наличия ошибок, отсутствующая
-- в данном примере!
DECLARE @ID uniqueidentifier;
-- Определяем уровень вложенности триггера
-- (используются средства MS SQL Server)
-- Выполняем только для внешнего удаления
-- (операция DELETE запрошена вне триггера)
IF TRIGGER_NESTLEVEL(OBJECT_ID('DeleteNode'))=1
BEGIN
-- Внимание! В реальном триггере нужно учесть,
-- что может быть удалено несколько строк
-- Получаем уникальный идентификатор
-- удаляемого элемента
SELECT @ID=ID FROM deleted;
-- Собираем список удаляемых узлов
-- во временной таблице #TempTBL
-- Удаляем временную таблицу
-- (на всякий случай, вдруг она существует)
DROP TABLE #TempTBL;
SELECT DISTINCT UID INTO #TempTBL FROM T_Helper
WHERE ParentID=@ID
-- Удаляем всех потомков удаляемого узла из
-- вспомогательной таблицы
DELETE FROM T_Helper WHERE UID IN (
SELECT * FROM #TempTBL);
-- Удаляем все записи вспомогательной таблицы для
-- удаляемого узла
DELETE FROM T_Helper WHERE UID=@ID;
-- Удаляем всех потомков из основной таблицы
-- Эта операция приводит к рекурсивному запуску
-- данного триггера
DELETE FROM T_Base WHERE ID IN (
SELECT * FROM #TempTBL);
-- Удаляем все записи основной таблицы
-- для удаляемого узла
-- Эта операция приводит к рекурсивному запуску
-- данного триггера
DELETE FROM T_Base WHERE ID=@ID;
END
ELSE
-- Случай рекурсивного вызова триггера
-- (триггер запущен операцией DELETE
-- выполненной в триггере)
BEGIN
-- Удаляем всех потомков из основной таблицы
DELETE FROM T_Base WHERE ID IN (
SELECT * FROM #TempTBL);
-- Удаляем все записи основной таблицы
-- для удаляемого узла
DELETE FROM T_Base WHERE ID=@ID;
END
Обратите внимание. При создании триггера используется параметр INSTEAD OF для того, чтобы триггер полностью заменял собой команду DELETE, приводящую к его запуску. Это нужно потому, что базовая и вспомогательная таблицы связаны между собой и удаление записей из базовой таблицы невозможно, если существуют основанные на них записи во вспомогательной таблице!
Удалим добавленный в предыдущем примере узел Z (рис. 83):
DELETE FROM T_Base WHERE Node='Z';
Рис. 83. Удаление узла Z
Теперь попробуем удалить узел C и всё поддерево, для которого этот узел является корнем (рис. 84):
DELETE FROM T_Base WHERE Node='C';
Рис. 84. Удаление поддерева
Проверим результат выполнения операции удаления, выбрав все узлы дерева, начиная с корня:
SELECT T_Base.Node, T_Helper.[Level]
FROM T_Base, T_Helper
WHERE T_Base.ID=T_Helper.UID and
T_Helper.ParentID=(
SELECT ID FROM T_Base WHERE Node='A')
ORDER BY T_Helper.[Level] ASC, T_Base.Node;
Результат не должен содержать узлов C F G H O M N P (рис. 85-86).
Рис. 85. Удаление узлов C F G H O M N P
Рис. 86. Иерархия после удаления поддерева с корневым узлом C
Контроль отсутствия петель в дереве может осуществляться проверкой записей во вспомогательной таблице – в ней не должно быть записей, в которых узел является сам себе предком с ненулевым расстоянием (рис. 87).
SELECT T_Base.Node, T_Helper.[Level]
FROM T_Base, T_Helper
WHERE T_Base.ID=T_Helper.UID AND
T_Helper.ParentID=T_Helper.UID AND
-- Исключаем корневые узлы
T_Helper.[Level]>0
ORDER BY T_Base.Node;
Рис. 87. Проверка на наличие/отсутствие петель
Тем не менее, возможность образования петель сохраняется, но на операциях выборки не может образоваться бесконечный цикл.
Данный способ, на сегодняшний день, считается наиболее универсальным для представления иерархий средствами реляционной СУБД. Однако он наследует такой недостаток способа со структурой со ссылкой на предка, как возможность образования петель. Трудности может вызвать поддержка целостности для полных путей от корня дерева до указанного узла. Кроме того, этот способ отличается некоторой избыточностью хранимых данных.
Задачи
Создайте таблицу, описывающую абстрактную иерархию со структурой со вспомогательной таблицей. Заполните её данными. На основе этой таблицы сформируйте и выполните SQL-предложения, решающие следующие задачи:
Определить корневой элемент иерархии.
Определить непосредственного предка некоторого заданного элемента.
Определить, что заданный элемент иерархии не имеет потомков.
Выбрать все элементы иерархии, не имеющие потомков (листья).
Выбрать всех потомков заданного элемента (выбрать поддерево, начиная с заданного узла).
Выбрать всех предков для заданного узла.
Определить расстояние от корня до заданного узла.
Определить уровень в иерархии заданного узла относительно другого узла, не являющегося предком данного.
Выбрать всех непосредственных потомков для некоторого заданного элемента.
Найти ближайшего общего предка для заданных узлов.
Удалить заданный узел. Учесть возможность существования потомков у удаляемого узла.
Добавить в иерархию новый элемент как потомка заданного узла. Написать триггер, добавляющий во вспомогательную таблицу строки для указания предков, не являющихся для добавляемого узла непосредственными.
Написать хранимую процедуру, проверяющую структуру на отсутствие петель.
Проверить все узлы иерархии на наличие нескольких предков.
Попробуйте решить предложенные задачи при условии, что в таблицах хранится несколько несвязанных иерархий.