Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Уральский Федеральный университет им. Б.Н. Ельцина «УПИ»

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Моделирование иерархических объектов средствами...doc

Скачиваний:

Добавлен:

08.09.2019

Размер:

9.85 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 128 9 10 11 12 > Следующая >>>

Задачи повышенной сложности

Выбрать всех непосредственных потомков для некоторого заданного элемента.
Найти ближайшего общего предка для нескольких наперёд заданных узлов.
Написать хранимые процедуры для пересчёта правого и левого коэффициентов при удалении узлов в иерархии.
Написать хранимые процедуры для пересчёта правого и левого коэффициентов при добавлении узлов в иерархию.
Рассмотреть вариант модели, когда значения правого и левого коэффициентов для листьев в дереве устанавливаются равными.

2.3. Способ вспомогательной таблицы

Способ, описанный Ральфом Кимбаллом, может рассматриваться как расширенный вариант рекурсивного способа. Здесь модель дерева строится на основе двух таблиц. Первая таблица (базовая) хранит список всех узлов, снабжённых уникальными идентификаторами, и всю содержательную информацию по каждому узлу.

Таблица 5

Пример основной таблицы

Уникальный идентификатор узла	Содержательная часть
A	A
B	B
C	C
D	D
E	E
F	F
G	G
H	H
I	I
J	J
K	K
L	L
M	M
N	N
O	O
P	P

Создадим эту таблицу:

CREATE TABLE T_Base

(ID uniqueidentifier DEFAULT NEWID() primary key,

Node varchar not null);

В этом примере для идентификаторов узлов дерева, хранимых в столбце ID, использован тип данных UNIQUEIDETIFIER, который будет заполняться автоматически при добавлении записей в таблицу (значение по умолчанию для этого столбца генерируется функцией NEWID()) и является первичным ключом.

Заполним таблицу данными (значения для столбца ID вводить не требуется):

INSERT INTO T_Base (Node) VALUES ('A');

INSERT INTO T_Base (Node) VALUES ('B');

INSERT INTO T_Base (Node) VALUES ('C');

INSERT INTO T_Base (Node) VALUES ('D');

INSERT INTO T_Base (Node) VALUES ('E');

INSERT INTO T_Base (Node) VALUES ('F');

INSERT INTO T_Base (Node) VALUES ('G');

INSERT INTO T_Base (Node) VALUES ('H');

INSERT INTO T_Base (Node) VALUES ('I');

INSERT INTO T_Base (Node) VALUES ('J');

INSERT INTO T_Base (Node) VALUES ('K');

INSERT INTO T_Base (Node) VALUES ('L');

INSERT INTO T_Base (Node) VALUES ('M');

INSERT INTO T_Base (Node) VALUES ('N');

INSERT INTO T_Base (Node) VALUES ('O');

INSERT INTO T_Base (Node) VALUES ('P');

Выберем все столбцы и строки полученной таблицы, отсортировав строки по полю Node:

SELECT * FROM T_Base ORDER BY Node;

Результат выполнения этого предложения SQL в среде SQL Server Management Studio Express представлен на рис. 75.

Рис. 75. Заполнение основной таблицы модели иерархии

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

Вспомогательная таблица по своей структуре похожа на таблицу со ссылкой на непосредственного предка, но, в отличие от неё, содержит все полные пути от корневого элемента до каждого узла иерархии в виде наборов пар «родитель-потомок». Здесь потомок может не быть непосредственным (прямым) потомком родителя, поэтому для каждой такой пары указывается расстояние («степень родства») от предка до потомка.

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

Первичный ключ во вспомогательной таблице составят все три столбца.

Структура такой таблицы и ее содержимое для иерархии, представленной на рис. 1, показана в таблице 6.

Таблица 6

Пример структуры вспомогательной таблицы

Уникальный идентификатор узла	Указатель на предка узла	Расстояние до предка
A	A или NULL	0
B	A	1
C	A	1
D	A	2
D	B	1
E	A	2
E	B	1
F	A	2
F	C	1
G	A	2
G	C	1
H	A	2
H	C	1
I	A	3
I	B	2
I	D	1
J	A	3
J	B	2
J	E	1
K	A	3
K	B	2
K	E	1
L	A	3
L	B	2
L	E	1
O	A	3
O	C	2
O	F	1
M	A	3
M	C	2
M	G	1
N	A	3
N	C	2
N	G	1
P	A	3
P	C	2
P	H	1

Создадим вспомогательную таблицу для уже имеющейся базовой таблицы с помощью следующего предложения SQL:

CREATE TABLE T_Helper (

UID uniqueidentifier references T_Base(ID) NOT NULL,

ParentID uniqueidentifier references T_Base(ID) NOT NULL,

[Level] int NOT NULL,

PRIMARY KEY (UID, ParentID, [Level]));

После заполнения данными базовая таблица имеет следующий вид:

Таблица 7

Таблица T_Base после заполнения данными

ID	Node
7F3FF030-0E7D-4BFF-B560-B43CA5E12CE4	A
06B5F4F9-4B40-4CC2-982F-F258CDAEBB1F	B
BB31DC0F-BB57-48FF-B768-79D205F17F33	C
07EDFC1D-2506-426E-BE2A-38BC86BA9EA2	D
777A3A0E-6079-43B9-8B9D-325230D48A3A	E
CF8D4BA4-89E3-4729-9B12-DDF2987D5949	F
9A42488B-536B-4269-A90C-BE164269425B	G
8E8CD289-7098-4C4F-A5A1-3DF2C25963AD	H
D9826E05-BFD1-4845-AEFC-215C2E5BA78B	I
AF1A9E1A-4747-4BC1-A5F5-FA30272BD4A8	J
AEB398A7-F653-4BE8-8844-AE9CAEC1A26F	K
2520E3D9-B40F-4A6A-ADD8-A334CABCFBB2	L
0FBD7863-B4B5-456A-8FAC-63B972AAD010	M
5BDF65BE-2940-48F3-BBB1-B3BA8B48287B	N
561D8D98-9410-4ECC-BA0E-CE4CC204705B	O
FC579270-CA86-4153-8DA3-BEA0F5DB6E24	P

Обратите внимание! Значения в столбце ID на каждом рабочем месте будут свои! Они также будут различаться и на одном рабочем месте при каждой новой попытке заполнения таблицы.

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

NSERT INTO T_Helper (UID, ParentID, Level) VALUES (

'7F3FF030-0E7D-4BFF-B560-B43CA5E12CE4',

'7F3FF030-0E7D-4BFF-B560-B43CA5E12CE4',0);