Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
4.1. Иерархическая модель данных
Иерархическая модель данных (ИМД) широко применяется на практике. Например, такая структура характерна для каталога папок Windows, с которой легко познакомиться, запустив Проводник.
Ограничимся тремя уровнями (рис. 4.1):
Рис. 4.1. Пример иерархической структуры данных
Примером ИМД является доменная система имен, подключенных к Интернету компьютеров.
Структура данных. В ИМД организацию данных принято определять в следующих терминах: атрибут, запись, групповое отношение, база данных [9]:
● атрибут или элемент данных или поле – это наименьшая единица данных. При этом каждому элементу в базах данных дается уникальное имя. По нему обращаются к БД при обработке;
● запись – это совокупность атрибутов. Применение записей обеспечивает за один запрос к базе данных получение некоторой логически связанной совокупности данных. В процессе функционирования именно записи изменяют, добавляют и удаляют. Состав атрибутов определяет тип записи. Каждый экземпляр записи – это конкретная запись с собственным значением элементов;
● групповое отношение – иерархическое отношение между отдельными записями двух типов. Запись «Родитель» (владелец группового отношения) называют исходной записью. Записи «Потомки» (члены группового отношения) – подчиненными.
Хранение данных в ИМД имеет вид древовидной структуры.
Дерево может рассматриваться как ориентированный граф, который описывается следующим образом:
а) корень – единственная вершина, в которую не входит ни одно ребро;
б) в остальные вершины входит только одно ребро, а исходит произвольное число ребер (зависимые вершины);
в) в структуре нет циклов.
Зависимые вершины, в которые входит одно ребро и не выходит ни одного, называются листьями.
В дереве (ИМД) вершины представляют собой таблицы описания экземпляров сущностей, дуги (ребра) – описывают связи между сущностями или адресные ссылки.
Пример ИМД. На внутреннем уровне иерархическая БД представляет один файл, который объединяет экземпляры записи одного типа, т.е. дерево в памяти ЭВМ представляется левосписочной структурой, как показано ниже.
Рис. 4.2. Иерархическая структура данных
файл
AB1C1C2B2C3B3C4C5C6 дерево 1 (групповое отношение)
дерево 2
............................................
дерево n
Корень каждого дерева содержит ключ с уникальным значением в обязательном порядке. Ключи некорневых записей могут иметь уникальное значение только в рамках одного группового отношения. Каждая запись идентифицируется полным сцепленным ключом, под которым понимается совокупность ключей всех записей от корневой записи по иерархическому дереву. Обращение к данным в древовидной структуре происходит через корневую вершину.
Пример. Предприятие состоит из нескольких отделов, в каждом из которых работают несколько сотрудников, при этом сотрудник не может работать более чем в одном отделе. Для создания информационной системы управления персоналом необходимо иметь групповое отношение (рис. 4.3, а), которое состоит из родительской записи ОТДЕЛ (Наименование отдела, Число работников) и дочерней записи СОТРУДНИК (Фамилия, Должность, Оклад). Для упрощения полагается, что имеются только две дочерние записи.
Для автоматизации процесса учета контрактов с заказчиками необходимо создание еще одной иерархической структуры: заказчик – контракты – сотрудники, работающие с ними. Такое дерево (рис. 4.3, б) включает следующие записи:
ЗАКАЗЧИК (Наименование заказчика, Адрес),
КОНТРАКТ (Номер, Дата, Сумма),
ИСПОЛНИТЕЛЬ (Фамилия, Должность, Наименование отдела).
Если необходимо показать, что некоторый сотрудник участвует в выполнении нескольких контрактов, то требуется ввод описания нового дерева 
(рис. 4.3, в).
Таким образом, модель данных включает в себя:
а) групповое отношение ОТДЕЛ – СОТРУДНИК;
б) групповое отношение ЗАКАЗЧИК – КОНТРАКТ – ИСПОЛНИТЕЛЬ;
с) групповое отношение ИСПОЛНИТЕЛЬ – КОНТРАКТ.
Из этого примера видны недостатки иерархических БД:
а) избыточность данных (структуры Сотрудник и Исполнитель дублируют друг друга);
б) если требуется организовать связь М:М, то в этом случае необходимо ввести описание нового дерева 
, как показано на рис. 4.3, в, что вынуждает дублировать информацию.
в) усложнение операций удаления и включения записи;
г) доступ к любой вершине осуществляется через корневую вершину, что увеличивает время доступа.
В иерархической модели определены следующие операции:
● добавление в базу данных новой записи. Для записи «корень» обязательно необходимо сформировать значения ключа;
● редактирование значений данных предварительно извлеченной записи. Ключевые данные не должны подвергаться изменениям;
● удаление некоторой записи со всеми подчиненными ей записями;
● извлечение:
– корневой записи по ключевому значению (допускается также последовательный просмотр корневых записей);
– следующей записи (следующая запись, в этом случае, извлекается в порядке левостороннего обхода дерева).
в б
Рис. 4.3. Иерархическая модель данных «Предприятие»
В операции ИЗВЛЕЧЕНИЕ допускается применение условий извлечения (например, выявить сотрудников с определенным окладом).
Таким образом, все операции модификации применяются только к одной «текущей» записи (которая должна быть предварительно извлечена из базы данных). Такой подход к манипулированию данных получил название «навигационного».
Ограничения целостности. В ИМД поддерживается только целостность связей между владельцами и членами группового отношения, следовательно, никакой потомок не может существовать без родителя. Как уже упоминалось, автоматически не обеспечивается соответствие парных записей, которые входят в различные ИМД.