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

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

Рисунок 1.3.6.1. Пример иерархической структуры

Рассмотрим ряд терминов иерархической модели.

Высота, вес и момент дерева ‑ число уровней, листьев и узлов в дереве.

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

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

Сбалансированное дерево - дерево, в котором любой исходный узел имеет одинаковую степень (одинаковое число ветвей или под­чи­нен­ных узлов).

Бинарное (двоичное) дерево ‑ сбалансированное дерево с исходными уз­ла­ми степени два. Любое дерево можно преобразовать в бинарное дерево. Поиск дан­ных в бинарном дереве наиболее быстрый.

Один экземпляр дерева хранится в виде списка данных узлов, полу­ченного левосторонним обходом дерева (сверху вниз и справа налево).

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

Иерархическая модель данных является наиболее простой среди всех даталогических моделей. Исторически она появилась первой: именно эту модель поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.

Рассмотрим основные понятия этой СУБД.

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

Поле данных - это минимальная, неделимая единица данных, доступная пользователю с помощью СУБД.

Сегмент – это запись,при этом определяются два понятия: тип сегмента или тип записи и экземпляр сегмента или экземпляр записи.

Тип сегмента - это поименованная совокупность типов элементов данных, в него входящих.

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

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

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

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

Каждая физическая БД удовлетворяет следующим иерархическим ограничениям:

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

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

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

В рамках иерархической модели выделяют языковые средства описания данных (DDL, Data Definition Language) и средства манипулирования данными (DML, Data Manipulation Language).

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

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

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

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

HDAM - hierarchical direct access method (иерархически прямой метод) - максимально быстрый, но не компактно хранящий данные;

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

HIDAM - hierarchical index direct access method (иерархически индексно-прямой метод) – компромиссный вариант, ближе к HDAM.

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

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

Представление внешней модели называется логической базой данных и определяется совокупностью блоков связи данного приложения с физическими БД, входящими в концептуальную схему БД. Блок связи – РСВ, program communication bloc – описывает связь с одной физической БД. Совокупность блоков РСВ образует полное внешнее представление данного приложения, называемое «блоком спецификации программ» (PSB, program specification block).

При формировании исполнимого файла прикладной программы модуль с описанием базы данных и подсхемы (PSB) включались в исполнимый файл и использовались при выполнении программы.

Для организации физического размещения иерархических данных в памяти ЭВМ могут использоваться следующие группы методов:

представление линейным списком с последовательным распределением памяти (адресная арифметика, левосписковые структуры);

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

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

поиск указанного экземпляра БД (например, дерева со значением 10 в поле Отд_номер);

переход от одного дерева к другому;

переход от одной записи к другой внутри дерева (например, к следующей записи типа Сотрудники);

ставка новой записи в указанную позицию;

удаление текущей записи и т. д.

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

К достоинствам иерархической модели данных относятся эффективное использование памяти ЭВМ и неплохие показатели времени выполнения основных операций над данными. Иерархическая модель данных удобна для работы с иерархически упорядоченной информацией.

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

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

Дата добавления: 2014-12-10