- •1. Основные понятия и определения 4
- •2. Три базовых способа моделирования иерархий 11
- •3. Два важных частных случая 125
- •1. Основные понятия и определения
- •1.1. Иерархическая модель данных
- •1.2. Реляционная модель данных
- •1.3. Задача моделирования
- •2. Три базовых способа моделирования иерархий
- •2.1. Рекурсивный способ представления иерархии1
- •Insert into @tree (Name, Level) values (@NodeName, @Level);
- •Insert into @tree (Name, Level) values
- •Insert @tree ([name], id, parent, [level], [order])
- •Insert @tree ([name], id, parent, [level], [order])
- •Insert @tree ([name], id, parent, [level], [order])
- •Insert @tree ([name], id, parent, [level], [order])
- •Insert @tree ([name], id, parent, [level], [order])
- •Insert into t(Parent, Data) values(1, 'b');
- •Id int not null,
- •Insert into @tree ([Name], id, Parent, [Level], [Check], [Path])
- •Values (@NodeName, @id, @Parent, @Level, @Check, @Path);
- •Insert into @tree ([Name],
- •Values (@NodeName,
- •Id int not null,
- •Id not in (select distinct Parent from t);
- •Insert into @tree ([Name],
- •Задачи повышенной сложности
- •2.2. Способ правого и левого коэффициентов
- •Задачи повышенной сложности
- •2.3. Способ вспомогательной таблицы
- •Insert into t_Base(Node) values (@NewRoot);
- •Insert into t_Helper(uid, ParentId, [Level])
- •Values (@RootId, @RootId, 0);
- •Instead of delete
- •3. Два важных частных случая
- •3.1. Случай ограниченного количества уровней иерархии
- •3.2. Случай ограниченного числа потомков
- •Заключение
- •Библиографический список
- •Ермаков Дмитрий Германович
- •620002, Екатеринбург, ул. Мира, 19
Insert into t(Parent, Data) values(1, 'b');
и выбрав значение в столбце Level, соответствующее добавленному узлу:
SELECT [Level] FROM T WHERE Data='B';
Результат операции представлен на рис. 35.
Рис. 35. Уровень узла в иерархии
В данной структуре присутствует, как минимум, один возможно опасный недостаток – отсутствие контроля правильности ссылки на родителя. Например, если в качестве предка узла B по какой-то причине указан узел K, получается петля, которая породит бесконечный цикл (табл. 7 и рис. 7). Проверку на существование петель можно осуществить, например написав соответствующую функцию, на основе функции для определения всех предков заданного узла.
CREATE FUNCTION MyCheckLoop (@NodeName varchar(1))
RETURNS @tree table
(
[Name] VARCHAR(1) NOT NULL,
Id int not null,
Parent int NOT NULL,
[Level] int NOT NULL,
[Check] int NOT NULL,
[Path] VARCHAR(4096) NOT NULL
)
AS
BEGIN
DECLARE @ID int;
DECLARE @Parent int;
DECLARE @Level int;
DECLARE @Check int;
DECLARE @Path VARCHAR(4096);
-- ВНИМАНИЕ! После каждой операции необходима
-- проверка наличия ошибок, отсутствующая
-- в данном примере!
-- По имени узла получаем его идентификатор и
-- идентификатор его непосредственного предка.
SELECT @ID=ID, @Parent=Parent
FROM T
Where Data=@NodeName;
-- Для самого узла указываем нулевое расстояние до предка
SET @Level=0;
-- Пока петель не найдено
SET @Check=0;
-- Путь в дереве
SET @Path=@NodeName;
-- Добавляем запись в возвращаемую таблицу
Insert into @tree ([Name], id, Parent, [Level], [Check], [Path])
Values (@NodeName, @id, @Parent, @Level, @Check, @Path);
-- Пока не доберёмся до корневого элемента иерархии
-- или не обнаружим повтор
WHILE (@ID <> @Parent)
BEGIN
SELECT @ID=ID, @Parent=Parent, @NodeName=Data
FROM T
WHERE ID=@Parent;
-- Наращиваем расстояние до предка
SET @Level=@Level+1;
-- Добавляем элемент пути
SET @Path=@Path+'::'+@NodeName;
-- Проверяем, нет ли уже записи об этом узле
-- в результирующей таблице
select @Check=COUNT([Check]) from @tree
where [Name]=@NodeName and
ID=@ID and
Parent=@Parent and
[Level]<>@Level;
-- Добавляем запись в возвращаемую таблицу
Insert into @tree ([Name],
ID,
Parent,
[Level],
[Check],
[Path])
Values (@NodeName,
@ID,
@Parent,
@Level,
@Check,
@Path);
-- Если обнаружена петля выходим из
-- цикла и завершаем работу функции
if @Check<>0 BREAK
END -- while
RETURN
END
На целой ветви от узла K до корня результат будет следующим (рис. 36)
SELECT * FROM MyCheckLoop('K');
Рис. 36. Проверка целостности структуры дерева – петель нет
Теперь испортим тестовую иерархию, создав петлю, как это показано в табл. 3 и на рис. 37-39.
Таблица 3
Пример образования петли
-
Уникальный идентификатор узла
Указатель на непосредственного предка узла
Содержательная часть
A
A или NULL
A
B
K
B
C
A
C
D
B
D
E
B
E
F
C
F
G
C
G
H
C
H
I
D
I
J
E
J
K
E
K
L
E
L
O
F
O
M
G
M
N
G
N
P
H
P
Рис. 37. Пример образования петли
Рис. 38. Создание петли, шаг 1
Рис. 39. Создание петли, шаг 2
В этом случае результат проверки будет таким, как показано на рис. 40.
Рис. 40. Обнаружение наличия петли в структуре иерархии
Наличие ненулевого значения в столбце Check свидетельствует о наличии петли в структуре данных. Значения в полях Path, ID и Parent позволяют локализовать и исправить ошибку.
Для того чтобы проверить целостность всего дерева, достаточно проверить отсутствие петель по всем путям от корня до листьев. Для этого строим список листьев и проверяем функцией MyCheckLoop каждый элемент этого списка.
CREATE FUNCTION CheckLoopTree()
RETURNS @tree table
(
[Name] VARCHAR(1) NOT NULL,