Информационное обеспечение систем управления

       

Иерархическая модель


Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.

Тип дерева состоит из одного «корневого» типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи [8].

Пример типа дерева (схемы иерархической БД) представлен на рис. 2.19.

Рис. 2.19. Пример схемы иерархической БД

На рис. 2.19 ОТДЕЛ является предком для НАЧАЛЬНИК и СОТРУДНИКИ, а НАЧАЛЬНИК и СОТРУДНИКИ - потомки ОТДЕЛ. Между типами записи поддерживаются связи.

База данных с такой схемой могла бы выглядеть следующим образом (рис. 2.20, показан один экземпляр дерева) [8].

Рис. 2.20. Реализация иерархической БД

Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для БД определен полный порядок обхода - сверху-вниз, слева-направо.

Примерами типичных операторов манипулирования иерархически организованными данными могут быть следующие [8].

–       Найти указанное дерево БД (например, отдел 42).

–       Перейти от одного дерева к другому.

–       Перейти от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику).

–       Перейти от одной записи к другой в порядке обхода иерархии.

–       Вставить новую запись в указанную позицию.

–       Удалить текущую запись.

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

В иерархических системах поддерживалась некоторая форма представлений БД на основе ограничения иерархии.
Примером представления приведенной выше БД может быть следующая иерархия (рис. 2.21) [8].



Рис. 2.21. Пример схемы иерархической БД

Экземпляр дерева базы данных не обязательно должен содержать все свои сегменты. При необходимости можно добавлять или удалять экземпляры типов записей в соответствии с требованиями приложения.

Иерархическая структура реализует отношение ОДИН-КО-МНОГИМ между исходным и порожденным типами записей. Это отображение полностью функционально, т.к. дерево не может содержать порожденный узел без исходного узла (за исключением «корня»). Следовательно, отображения ОДИН-К-ОДНОМУ и ОДИН-КО-МНОГИМ могут непосредственно представляться иерархическими структурами. Однако для представления отображения МНОГИЕ-КО-МНОГИМ необходимо дублирование деревьев, а значит, реализация сложных связей требует больших затрат памяти.

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


Содержание раздела