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

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

Иерархическая модель появилась впервые в результате обобщения структур данных языка Кобол.

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

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

С точки зрения теории графов иерархическая модель представляет собой древовидный граф (перевернутое дерево), упрощенный вид которого показан на рис. 10.

Рис. 10. Древовидный граф

Реальный пример иерархической модели данных представлен на рис. 11 и 12.

Рис. 11. Пример иерархической модели данных

Рис. 12. Пример иерархической модели данных

Над иерархически организованными данными определенны следующие операции:

· Добавить в базу данных новую запись.

· Изменить значение данных предварительно извлеченной записи.

· Удалить некоторую запись и все подчиненные ей записи.

· Извлечь запись; в этой операции допускается задание условий выборки, например, извлечь сотрудников с окладом более 200 тысяч руб.

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

· достаточно эффективное использование памяти и

· неплохие временные показатели выполнения операций над данными.

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

Основными информационными единицами в иерархической модели являются:

· база данных (БД),

· сегмент,

· поле.

Поле данных определяется как минимальная, неделимая единица данных, доступная пользователю с помощью СУБД. Например, если в задачах требуется печатать в документах адрес клиента, но не требуется дополнительного анализа полного адреса, то есть города, улицы, дома, квартиры, то мы можем принять весь адрес за элемент данных, и он будет храниться полностью, а пользователь сможет получить его только как полную строку символов из БД. Если же в наших задачах существует анализ частей, составляющих адрес, например города, где расположен клиент, то нам необходимо выделить город как отдельный элемент данных, только в этом случае пользователь может получить к нему доступ и выполнить, например, запрос на поиск всех клиентов, которые проживают в конкретном городе, например в Париже. Однако если пользователю понадобится и полный адрес клиента, то остальную информацию по адресу также необходимо хранить в отдельном поле, которое может быть названо, например, Сокращенный адрес. В этом случае для каждого клиента в БД хранится как Город, так и Сокращенный адрес.

Сегмент в терминологии Американской Ассоциации по базам данных DBTG (Data Base Task Group) называется записью, при этом в рамках иерархической модели определяются два понятия:

· тип сегмента или тип записи,

· экземпляр сегмента или экземпляр записи.

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

Очень важно понимать различие между сегментом и типом сегмента — оно такое же, как между типом переменной и самой переменной: сегмент является экземпляром типа сегмента. Например, у нас может быть тип сегмента Группа (Номер, Староста) и сегменты этого типа, такие как (4305, Петров Ф. И.) или (383, Кустова Т. С).

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

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

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

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

Рис. 13.Пример иерархических связей между сегментами

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

· в каждой физической БД существует один корневой сегмент, то есть сегмент, у которого нет логически исходного (родительского) типа сегмента;

· каждый логически исходный сегмент может быть связан с произвольным числом логически подчиненных сегментов;

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

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

Рис. 14.Пример структуры иерархического дерева

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

На рис. 9 представлены 2 экземпляра иерархического дерева соответствующей структуры.

Рис. 15.Пример двух экземпляров данного дерева

Экземпляры-потомки одного типа, связанные с одним экземпляром сегмента-предка, называют "близнецами".

Так, для нашего примера экземпляры b1, b2 и b3 являются "близнецами", но экземпляр b4 подчинен другому экземпляру родительского сегмента, и он не является "близнецом" по отношению к экземплярам b1, b2 и b3.

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

Так, используя принцип линейной записи иерархических графов, пример на рис. 9 можно представить в виде двух записей:

а1 b1 b2 b3 c1 d1 d2 e1	a2 b4 b5 c2 c3 d3 d4 e2 e3 e4
Запись 1	Запись 2

Как видно из нашего примера, физические записи в иерархической модели различаются по длине и структуре.