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

Иерархическая модель (ИМД) представляет собой связный граф в виде дерева (рис.).

Рис. Дерево

Основные особенности (ограничения) иерархической модели БД:

1. Структура связей древовидная. На верхнем 1-ом уровне только один узел – корень. Верхние элементы дерева называются исходными, а нижние – порожденными элементами (иначе родители и потомки).

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

3. Допустимы бинарные связи типа «один к одному» («1:1»), «один ко многим» («1:М»), «многие к одному» («М:1»).

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

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

Пример иерархической структуры - информация об отделах и служащих, при условии, что каждый сотрудник работает в одном отделе и каждая работа выполняется только в одном отделе, т.е. все связи типа «1:М». Иерархия представления информации об отделах и его служащих показана на рис.

Отдел

Служащие Работы

Трудовая деятельность Дети

Отдел

Сотрудники Начальник

Рис. Иерархическое представление данных об отделах и служащих

Базовые конструкции в ИМД (все конструкции именованные):

- поле;

- сегмент (тип запись);

- база данных (тип дерево).

Поле - минимальная неделимая единица информации, доступная пользователю, например, фамилия служащего.

Сегмент данных - это совокупность полей для описания некоторого класса объектов, например сегмент «Служащие».

Сегменты объединяются в древовидный граф без циклов и петель. Каждое дерево называется физической БД.

Различают тип сегмента и экземпляры сегмента. Например, тип сегмента «Служащие», а экземпляры – каждый конкретный служащий. Каждый тип сегмента характеризуется фиксированной длиной и фиксированным разбиением на поля.

Физическая запись в ИМД (иерархическая запись) образована экземпляром корневого сегмента и совокупностью всех подчиненных ему экземпляров порожденных сегментов. Физические записи в ИМД могут различаться по структуре и длине. Например, в отделе САПР 10 сотрудников, выполняется 2 работы, а в отделе АСУ - 25 сотрудников и решается 5 задач.

Между записями различных деревьев целостность связей не поддерживается.

Первая СУБД - IMS фирмы IBM поддерживала иерархическую модель, наиболее известные отечественные СУБД ИМД - СУБД ОКА и ИНЕС.

Достоинство ИМД – простота и естественность отображения взаимосвязи между объектами.

Недостатки ИМД:

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

2. Асимметричность - основной недостаток иерархического подхода, затрудняет работу пользователя. Рассмотрим два симметричных запроса: «найти всех служащих данного отдела» и «найти отдел данного служащего». Возможность доступа к информации любого узла только от корня увеличивает время ответа, особенно на второй из перечисленных запросов.

3. Неоднозначность моделирования связей типа «многие ко многим» (типа «М: N»). Например, между поставщиками и деталями существует связь типа «М:N». Возможно построение двух иерархических структур: в первой модели исходные узлы - поставщики, а подчиненные – детали, которые они поставляют, в другой модели исходные узлы - детали, а подчиненные – поставщики, которые их поставляют. Каждая модель имеет недостатки при выполнении одного из симметричных запросов: «найти всех поставщиков данной детали» или «найти все детали данного поставщика».

4. Аномалии выполнения операций включения, удаления, обновления. Например, при удалении поставки некоторой детали, удаляется информация о поставщике, если это единственная его поставка и т.п.

Дата добавления: 2014-01-07