Главная » Microsoft SQL Server, Базы данных » Шаблон смежных списков

0

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

Основные шаблоны смежных списков

До сих пор самой распространенной схемой хранения иерархических данных остаются шаблоны смежных списков, неформально называемые парами данных и моделями с собственным объединением. Они хранят ключ текущего узла и его непосредственного предка в строке текущего узла (в этой главе мы будем обращаться к элементам пары данных как к текущему и родительскому узлам).

Эта схема хорошо известна вам по таблице Employee учебной базы данных Northwind. В ней в полях EmployeelD и ReportsTo хранятся соответственно идентификаторы сотрудника и его непосредственного начальника (рис. 12.1).

Рис. 12.1. Таблица Employee базы данных Northwind является прекрасным примером использования схемы шаблона смежных списков для хранения организационной диаграммы

Между работником, выступающим в роли начальника, и сотрудником, который перед ним отчитывается, существует отношение “один ко многим”. Начальник может иметь много подчиненных, однако каждый работник имеет только одного непосредственного начальника. Любой работник может быть одновременно и начальником и подчиненным.

Столбец ReportsTo является внешним ключом таблицы и ссылается на столбец Employee ID той же таблицы. В столбце Report sTo хранится идентификатор Employee ID непосредственного начальника. Если узел работника является текущим, то столбец Report sTo указывает на родительский узел. Этот столбец может содержать пустое значение, поскольку глава всей организации ни перед кем не отчитывается.

С точки зрения начальника, его идентификатор хранится в поле Report sTo всех его подчиненных.

Вариации смежных списков

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

Таблица 12.1. Иерархические схемы

Шаблон

Для чего пригоден

Базовый смежный список или материализованный путь

Смежный список с двумя родителями или двойной материализованный путь

Ассоциативные таблицы

Объектно-ориентированные классы, простые организационные диаграммы, деревья видов

Генеалогии

Списки материалов, сложные организационные диаграммы

Двойные предки

Биологические генеалогии (т.е. мы не рассматриваем приемных родителей) требуют хранения двух предков: мужской и женской особи, что, в свою очередь, требует наличия двух внешних ключей. Учебная база данных Family использует эту модель. Так как внешние ключи ссылаются на ту же таблицу, они должны быть добавлены при ее создании. Следующий код извлечен из сценария создания базы данных Family:

CREATE TABLE dbo.Person (

PersonID INT NOT NULL

PRIMARY KEY NONCLUSTERED,

LastName VARCHAR(15) NOT NULL,

FirstName VARCHAR(15) NOT NULL,

SrJr VARCHAR(3) NULL,

MaidenName VARCHAR(15) NULL,

Gender CHAR(l) NOT NULL,

FatherID INT NULL,

MotherlD INT NULL,

DateOfBirth DATETIME NULL,

DateOfDeath DATETIME NULL

CREATE CLUSTERED INDEX IxPersonName ON dbo.Person (LastName, FirstName);

ALTER TABLE dbo.Person ADD CONSTRAINT

FK_Person_Father FOREIGN KEY (FatherlD) REFERENCES dbo.Person (PersonID);

ALTER TABLE dbo.Person ADD CONSTRAINT

FK_Person_Mother FOREIGN KEY (MotherlD) REFERENCES dbo.Person (PersonID);

В базе данных Family каждая запись ссылается на два родительских узла: биологической матери и биологического отца. Оба внешних ключа указывают на один и тот же первичный ключ (рис. 12.2).

Puc. 12.2. Шаблон смежного списка с двумя родителями можно использовать для хранения генеалогий (в частности, он использован в учебной базе данных Family)

Можно доказать, что данный шаблон нарушает первую нормальную форму, поскольку оба столбца— MotherlD и FatherlD — хранят внешний ключ PersonID. Однако отношения к матери и к отцу уникальны, и разница в поколениях приводит к тому, что каждый внешний ключ реально указывает на отличное подмножество таблицы Person, что может и должно поддерживаться триггером.

Если вы хотите загрузить эти учебные базы данных и поэкспериментировать с ЩцТТ”В ними, а также опробовать на них созданные мною запросы, использующие раз- .N/Wce™ ные вариации шаблона смежных списков, зайдите на сайт этой книги по адресу

^     www.SQLServerBible.com.

Ассоциативные таблицы

При наличии отношений “многие ко многим” между текущими и родительскими узлами требуется наличие ассоциативной таблицы (аналогичным образом реализуются отношения “многие ко многим” и в любой другой модели). Например, заказ может содержать множество товаров, а любой товар может входить во множество заказов. Поэтому таблица строк заказа выступает в роли ассоциативной между таблицами заказов и товаров.

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

В иерархическом списке материалов сам этот список выступает в роли смежной таблицы между текущим и родительскими узлами, которые хранятся в одной и той же таблице Material (рис. 12.3).

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

Шаблон материализованного пути

Шаблон материализованного пути представляет собой еще один прекрасный метод хранения иерархических данных и навигации по ним. В своей основе он хранит денормализован- ный список всех предков текущего узла, включая все их поколения. Например, в хорошо знакомой таблице Employee базы данных Northwind столбец MaterializedPath хранит путь в организационной диаграмме от корневого до текущего узла. Этот столбец был добавлен в таблицу исключительно с целью демонстрации модели материализованного пути— само это решение не требует наличия столбца ReportsTo.

EmployeelD LastName FirstName ReportsTo MaterializedPath

1                 Davolio           Nancy           2                    21

2                 Fuller              Andrew         NULL             2

3                 Leverling         Janet             2                    23

4                 Peacock           Margaret       2                    24

5               Buchanan                               Steven                             2                                          25

6               Suyama                                  Michael 5                                                                     256

7               King                                        Robert                              5                                          257

8               Callahan                                 Laura                               2                                          28

9               Dodsworth Anne                                                             5                                          259

Шаблон материализованного пути имеет свои достоинства и недостатки. Положительным является то, что существует несколько хороших методов манипуляции иерархией и ее анализа с помощью строковых функций. Ограничение like в предложении where быстро найдет всех, кто отчитывается перед мистером Buchanan без необходимости прохождения по всем уровням иерархии.

SELECT * FROM Employees WHERE MaterializedPath Like ‘ 25_!

Результат выполнения запроса будет следующим:

EmployeelD LastName                           FirstName ReportsTo MaterializedPath

6                Suyama                                 Michael 5                                                                     256

7               King                                        Robert                              5                                          257

9         Dodsworth Anne 5 259

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

Источник: Нильсен, Пол. Microsoft SQL Server 2005. Библия пользователя. : Пер. с англ. — М. : ООО “И.Д. Вильямс”, 2008. — 1232 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии