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

     2.2 Сегмент иерархической  модели

     Основными информационными единицами являются сегмент, поле, дерево.

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

     Структурные связи определяются подчиненностью, в силу чего сегмент более низкого  уровня называют порожденным, а более высокого уровня - исходным. Сегмент самого верхнего уровня носит название «корневой». Именно через него осуществляется доступ к иерархической БД (точка входа). Экземпляр порожденного сегмента не может существовать в отсутствие экземпляра исходного сегмента. В силу этого положения при удалении экземпляра исходного сегмента удаляются и все экземпляры порожденных сегментов.

     Сегмент (DBTS) -называется записью.

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

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

     1) имеется единственная особая  вершина, называемая корнем, в  которую не заходит ни одно  ребро;

     2) во все остальные вершины заходит  только одно ребро, а исходит  произвольное (0, 1, 2, ..., n) количество ребер;

     3) не имеется циклов.

     В программировании используется другое определение дерева, позволяющее  при решении задач рассматривать  дерево как структуру, состоящую  из меньших деревьев (или поддеревьев), т.е. как рекурсивную структуру.

     Рекурсивно  дерево определяется как конечное множество T, состоящее из одного или более узлов (вершин), таких, что:

     1) существует один специально выделенный  узел, называемый корнем дерева;

     2) остальные узлы разбиты на m ≥  0 непересекающихся подмножеств  Т1 , Т2 , ..., Тm , каждое из которых в свою очередь является деревом.

     Деревья Т1 , Т2 , ..., Тm называются поддеревьями корня.

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

     Таким образом, иерархическая древовидная  структура, ориентированная от корня, удовлетворяет следующим условиям:

     - узел состоит из одного или нескольких атрибутов;

     - иерархия всегда начинается с корневого узла;

     - на верхнем уровне может находиться только один узел - корневой;

     - на нижних уровнях находятся порожденные (зависимые) узлы: они могут добавляться в вертикальном и горизонтальном направлениях без ограничения;

     - каждый порожденный узел, находящийся на уровне i, связан только с одним непосредственно исходным узлом (непосредственным родительским узлом), находящимся на верхнем уровне (i-1) иерархии дерева;

     - каждый исходный узел может иметь один или несколько непосредственно порожденных узлов, которые называются подобными (связи 1:M);

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

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

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

     

     Рисунок 2.4 - Пример структуры иерархического дерева 

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

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

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

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

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

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

     Пример  типа дерева (схемы иерархической БД):

     

     Рисунок 2.5- Пример схемы иерархической БД

     Здесь Отдел является предком для Начальник  и Сотрудники, а Начальник и  Сотрудники - потомки Отдел. Между  типами записи поддерживаются связи.

     База  данных с такой схемой могла бы выглядеть следующим образом (мы показываем один экземпляр дерева):

     

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

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

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

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

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

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

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

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

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

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

     -Физическая упорядоченность строк всех таблиц может определяться и для всей БД (так делается, например, в Datacom/DB).

     -Для  каждой таблицы можно определить  произвольное число ключей поиска, для которых строятся индексы.  Эти индексы автоматически поддерживаются  системой, но явно видны пользователям.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     -END — конец.

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

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