- •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
Id int not null,
Parent int NOT NULL,
[Level] int NOT NULL,
[Check] int NOT NULL,
[Path] VARCHAR(4096) NOT NULL
)
AS
BEGIN
DECLARE @Data varchar(1);
-- ВНИМАНИЕ! После каждой операции необходима
-- проверка наличия ошибок, отсутствующая в данном примере!
-- Последовательно выбираем все листья
-- Для этого создаём курсор
declare c1 cursor
keyset
for
SELECT DISTINCT Data FROM T WHERE
Id not in (select distinct Parent from t);
-- Открыли курсор
open c1
-- Выбрали первый лист
fetch next from c1 into @data;
while (@@fetch_status <> -1)
-- Пока не перебрали все листья...
begin
Insert into @tree ([Name],
ID,
Parent,
[Level],
[Check],
[Path])
SELECT [Name],
ID,
Parent,
[Level],
[Check],
[Path]
FROM MyCheckLoop(@data);
-- Следующий лист...
fetch next from c1 into @data;
end
deallocate c1;
return
end
Выполним эту функцию для дерева без петель:
SELECT * FROM CheckLoopTree();
Результат выполнения представлен на рис. 41.
Теперь снова, как в предыдущем примере, испортим тестовую иерархию, создав петлю, и повторим проверку (рис. 42):
SELECT * FROM CheckLoopTree();
Рис. 41. Проверка целостности дерева, петли отсутствуют
Рис. 42. Проверка целостности дерева, обнаружены петли
Ненулевые значения в столбце Check свидетельствует о наличии, по крайней мере, одной петли в структуре данных (см. рис. 42). Значения в полях Path, ID и Parent позволяют локализовать и исправить ошибку.
Действительно ли это недостаток подхода? Благодаря этому свойству в таблице можно хранить несколько различных иерархий и даже более сложные сетевые структуры, допускающие для каждого узла более одного предка.
Задачи
Создайте таблицу, описывающую абстрактную иерархию со структурой со ссылкой на предка. Заполните её данными. На основе этой таблицы сформируйте и выполните SQL-предложения, решающие следующие задачи:
Определить корневой элемент иерархии.
Выбрать непосредственных потомков для некоторого заданного элемента.
Определить непосредственного предка некоторого заданного элемента.
Добавить в иерархию новый элемент как потомка заданного узла.
Определить, что заданный элемент не имеет потомков.
Выбрать все элементы иерархии, не имеющие потомков (листья).
Задачи повышенной сложности
Определить уровень в иерархии одного заданного элемента относительно другого заданного элемента.
Определить ближайшего общего предка для двух наперёд заданных узлов.
Добавить в иерархию новый элемент как потомка заданного узла с автоматическим заполнением поля уровня в иерархии.
Написать хранимую процедуру, извлекающую всё поддерево, начиная с заданного узла.
Удалить заданный элемент иерархии. Учесть возможность наличия потомков удаляемого элемента.
Написать хранимую процедуру, проверяющую структуру на отсутствие петель.
Проверить все узлы иерархии на наличие нескольких предков.