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

C. Сетевые структуры.

B. Деревья.

 

Дерево (рис. 4.1) представляет собой иерархию элементов, называемых узлами. На самом верхнем уровне иерархии имеется только один узел – корень, являющийся входом в структуру. Каждый узел, кроме корня, связан с одним узлом на более высоком уровне, называемым исходным узлом для данного узла. Каждый элемент имеет только один исходный. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне, которые называются порожденными. Между исходным узлом и порожденными узлами имеется отношение «один – ко – многим». Связи между узлами называются дугами или ребрами. Между двумя узлами может быть только одна связь. Любая часть дерева, исходящая из одного узла (кроме корня), называется ветвью. Элементы, расположенные в конце ветви, т.е. не имеющие порожденных, называются листьями.

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

 

рис. 4.1. Структура типа дерево.

 

Пример иерархической БД показан на рис. 4.2.

рис. 4.2. Пример иерархической БД.

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

- найти указанное дерево БД (например, отдел с заданным номером);

- перейти от одного дерева к другому;

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

- перейти от одной записи к другой в порядке обхода иерархии;

- вставить новую запись в указанную позицию;

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

Система IMS (Information Management System) является самой первой коммерческой СУБД, она до сих пор остается основной иерархической СУБД, используемой на большинстве крупных мейнфреймах. Эта система появилась в качестве программного обеспечения для осуществления проекта полета корабля Apollo на Луну. Основная идея этой системы была построена на том, что малые компоненты объединяются вместе как части более крупных компонентов до тех пор, пока не будет собран воедино весь проект. Т.е. использовалась иерархическая структура.

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

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

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

 

Недостатки иерархической модели данных:

 

1. Иерархическая модель данных не дает адекватных средств для явного указания ограничений, накладываемых на данные.

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

3. Трудность моделирования связей типа «многие – ко – многим». Включение связей такого типа приводит к необходимости дублирования данных.

 

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

На иерархической модели данных основано сравнительно ограниченное количество СУБД, в числе которых можно назвать зарубежные системы IMS, PC/Focus, Team-Up и data Edge, а также отечественные системы Ока, ИНЭС и МИРИС.