Федеральное агентство по образованию

Уральский государственный технический университет - УПИ

Д.Г. Ермаков

МОДЕЛИРОВАНИЕ ИЕРАРХИЧЕСКИХ ОБЪЕКТОВ

СРЕДСТВАМИ РЕЛЯЦИОННЫХ СУБД

Научный редактор проф., д-р техн. наук Ю.И. Кузякин

Печатается по решению редакционно-издательского совета

УГТУ-УПИ от 18.01.2007 г.

Екатеринбург

УГТУ-УПИ

2007

УДК 004.652(075.8)

ББК 32.973-018.2я73

Е72

Рецензенты:

Институт математики УрО РАН, зав. лаб. компьютерных технологий, с. н. с. А.М. Устюжанин, к. ф.-м. н..

Ермаков Д.Г.

Е72 Моделирование иерархических объектов средствами реляционных СУБД: учебное пособие/ Д.Г. Ермаков. Екатеринбург: УГТУ-УПИ, 2007.-132 с.

ISBN

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

Издание предназначено для студентов специальностей 230201 – Информационные системы и технологии и 080801 – Прикладная информатика в экономике.

Библиогр.: 13 назв. Табл. 16. Рис. 87.

Подготовлено кафедрой «Анализ систем и принятие решений»

УДК 004.652(075.8)

ББК 32.973-018.2я73

ISBN

© ГОУ ВПО «Уральский государственный технический университет – УПИ», 2007

© Д.Г. Ермаков 2007 г.

Оглавление

1. Основные понятия и определения 4

1.1. Иерархическая модель данных 4

1.2. Реляционная модель данных 9

1.3. Задача моделирования 9

2. Три базовых способа моделирования иерархий 11

2.1. Рекурсивный способ представления иерархии 11

2.2. Способ правого и левого коэффициентов 64

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

3. Два важных частных случая 125

3.1. Случай ограниченного количества уровней иерархии 125

3.2. Случай ограниченного числа потомков 128

Заключение 130

Библиографический список 136

1. Основные понятия и определения

1.1. Иерархическая модель данных

"Дерево" может быть определено как иерархия узлов с попарными связями, в которой:

• самый верхний уровень иерархии имеет единственный узел, называемый корнем;

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

И т.д.

"Дерево" может быть представлено как специальный вид направленного графа. Графы – структуры данных, состоящие из узлов, связанных дугами. Каждая дуга показывает однонаправленную связь между двумя узлами. Вершина графа называется корнем (рис. 1). Остальные элементы называют узлами иерархии.

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

Узел, связанный с данным узлом и находящийся на более высоком уровне в иерархии, называют родительским узлом или предком данного узла. Потомки, или дети, родительского узла – все узлы в поддереве, имеющие родительский узел корнем.

Узлы дерева, которые не имеют потомков, называют листьями (рис. 1).

В общем случае, дерево называется n-мерным, если его некоторый узел может иметь не более чем n узлов - потомков. Все элементы иерархии показаны на рис. 2 – 5.

Рис. 1. Основные элементы иерархии

Рис. 2. Уровни иерархии

Рис. 3. Диаграмма максимального пути

Рис. 4. Глубина пути в иерархии

Рис. 5. Семейство и размерность семейства иерархии

Рис. 6. Стандартное графическое представление иерархии в ОС MS Windows

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

Рис. 7. Представление иерархии как набора вложенных множеств

В качестве примеров использования иерархий для моделирования объектов реального мира можно отметить организационные диаграммы (графы), генеалогические деревья, карты как описания географических объектов и т.п.

Для работы с данными этого типа еще в 60-70 гг. прошлого века были разработаны иерархические СУБД, например IBM IMS, выполняющаяся на компьютерах IBM с архитектурой System/360, System/370, System/390, System z. Однако подобные продукты в настоящее время в нашей стране не имеют широкого распространения. Другие средства работы с иерархиями предоставляются XML.

1.2. Реляционная модель данных

Реляционные СУБД создавались таким образом, чтобы пользователи воспринимали их как совокупность таблиц. Архитектура реляционных баз данных ориентирована на хранение в отношениях (таблицах) информации о сущностях и связях между ними. Важной особенностью реляционной модели является наличие простого и мощного языка запросов SQL.