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

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

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

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

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

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

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

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

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

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

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

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

Экземпляры-потомки одного типа, связанные с одним Экземпляром сегмента-предка, называют «близнецами». Так, для нашего примера экземпляры Б1, Б2 и БЗ являются «близнецами», но экземпляр Б4 подчинен другому экземпляру родительского сегмента, и он не является «близнецом» по отношению к экземплярам Б1, Б2 и БЗ. Набор всех экземпляров сегментов, подчиненных одному экземпляру корневого сегмента, называется физической записью. Количество экземпляров-потомков может быть разным для разных экземпляров родительских сегментов, поэтому в общем случае физические записи имеют разную длину. Так, используя принцип линейной записи иерархических графов, можно представив в виде двух записей:

Таблица 1.  Принцип линейной записи иерархических графов

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

2.3. Сравнение иерархической и сетевой модели данных

Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия модели и формальный язык описания. Сетевая модель описывает элементарные данные и отношения между  ними  в виде ориентированной сети. Это такие отношения между объектами, когда каждый порожденный элемент имеет более одного исходного и может быть связан с любым другим элементом структуры.

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

Для сетевых моделей стоит выделить следующие проблемы:

      Сетевые модели не имеют общей теории.

      Много эвристики.

      Проблема эффективности процедур работы с сетями.

      Много видов сетей, в том числе рассчитанных на аппаратную реализацию.

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

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

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

Отличительные особенности иерархической и сетевой моделей: основной единицей обработки в них является запись; в иерархической модели данные организованы в иерархические структуры и обработка начинается только с корневой записи, а доступ к некорневым обеспечивается только по иерархическому пути; в сетевой модели данных обработка может быть начата с записи любого типа независимо от её расположения в БД, и от извлеченной записи возможны переходы, как к её подчиненным записям, так и к тем, которым она подчинена; при отображении сетевых структур предметной области в иерархической БД необходимо дублирование данных, при этом семантическая целостность автоматически не поддерживается.

2.4. Язык описания данных иерархической модели

Каждая физическая база описывается набором операторов, определяющих как ее логическую структуру, так структуру хранения БД. Описание начинается с оператора DBD (Data Base Definition):

DBD Name = < имя БД>  ACCESS = < способ доступа>

Способ доступа определяет способ организации взаимосвязи физических записей.

Определено 5 способов доступа:

      HSAM - hierarchical sequential access method (иерархически последовательный метод),

      HISАМ - hierarchical index sequential access method (иерархически индексно-последовательный метод),

      HDAM - hierarchical direct access method (иерархически прямой метод),

      HIDAM - hierarchical index direct access method (иерархически индексно-прямой метод),

      INDEX - индексный метод.

Далее идет описание наборов данных, предназначенных для хранения БД: DATA SET DD1  < имя оператора, определяющего хранимый набор данных, DEVICE =< устройство хранения БД>. OVERLOW = < имя области переполнения>.

Так как физические записи имеют разную длину, то при модификации данных запись может увеличиться и превысит исходную длину записи до модифика­ции. В этом случае при определенных методах хранения может понадобиться дополнительное пространство хранения, где и будут размешены дополнительные данные. Это пространство и называется областью переполнения

После описания всей физической БД идет описание типов сегментов, ее состав­ляющих, в соответствии с иерархией. Описание сегментов всегда начинается с описания корневого сегмента, Общая схема описания типа сегмента такова:

SEGM NAMЕ = < имя сегмента> BYTES =< размер в байтах>, FREQ - <средняя частота реализаций сегмента под одним исходным> PARENT = <имя родительского сегмента>.

Параметр FREQ определяет среднее количество экземпляров данного сегмента, связанных с одним экземпляром родительского сегмента. Для корневого сегмента это число возможных экземпляров корневого сегмента.

Для корневого сегмента параметр PARENT равен 0 (нулю). Далее для каждого сегмента дается описание полей:

FIELD NAME = {(<имя поля> [. SEQ].{U | M}) | <имя поля> }. START = < номер байта, с которого начинается значения поля >, BYTES = <размер поля в байтах>, TYPE = {X | Р | С}.

Признак SEQ — задается для ключевого поля, если экземпляры данного сегмента физически упорядочены в соответствии со значениями данного поля.

Параметр U задается, если значения ключевого поля уникальны для всех экземпляров данного сегмента, М — в противном случае. Если поле является ключевым, то его описание задается в круглых скобках, в противном случае имя поля задается без скобок. Параметр TYPE определяет тип данных. Для ранних иерархических моделей были определены только три типа данных; X — шестнадцатеричный, Р — упакованный десятичный, С — символьный.

Заканчивается описание схемы вызовом процедуры генерации:

DBDGEN — указывает на конец последовательности управляющих операторов описания БД;

FINISH — устанавливает ненулевой код завершения при обнаружении ошибки; Q END — конец.

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

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

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