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

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

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

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

• во все остальные вершины заходит только одно ребро, а исходит произвольное количество ребер;

• граф не содержит циклов.

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

В иерархических моделях данных используется ориентация древо-видной структуры от корня к листьям. Графическая диаграмма концептуальной схемы базы данных называетсядеревом определения. Пример иерархической базы данных приведён на рис. 2.6. Каждая некорневая вершина в ИМД связана с родительской вершиной (сегментом) иерархическим групповым отношением. Каждая вершина дерева соответствует типу сущности ПО. Тип сущности характеризуется произвольным количеством атрибутов, связанных с ней отношением 1:1. Атрибуты, связанные с сущностью отношением 1:n, образуют отдельную сущность (сегмент) и переносятся на следующий уровень иерархии. Реализация связей типа n:m не поддерживается.

Пример фрагмента иерархической базы данных

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

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

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

Корневая запись дерева должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальные значения только в экземплярах групповых отношений, т.е. на одном и том же уровне иерархии в разных ветвях дерева могут быть экземпляры записей с одинаковыми ключами. Это объясняется тем, что каждая запись идентифицируется полным сцепленным ключом, который образуется путём конкатенации всех ключей экземпляров родительских записей. Например, для студента (рис. 2.6) ключ – это (Шифр_факультета+Номер_курса+Номер_группы+Номер_зачётной_книжки).

Основным недостатком ИМД является дублирование данных. Оно вызвано тем, что каждая сущность (атрибут) может относиться только к одной родительской сущности. Например, если в БД хранятся данные о детях сотрудников, а на предприятии работает и отец, и мать ребёнка, то сведения об этом ребёнке нужно хранить дважды. Аналогичная ситуация возникает, если нужно отразить в БД связь «многие-ко-многим». Дублирование данных может вызвать нарушение логической целостности БД при внесении изменений в эти данные.

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

В качестве примера типичного представителя иерархических СУБД можно привести систему IMS (Information Management System, IBM).

Сетевая и иерархическая модели данных относятся к базам данных I-го поколения (60-е – начало 70-х гг. XX века). Эти модели не смогли в полной мере реализовать независимость данных от программ. Из-за особенностей их организации структура запросов к данным в таких системах определяется наличием связей между записями.

23. Реляционная модель данных (РМД)

Понятие отношения Реляционная модель данных была предложена в 1970 г. математиком Эдгаром Коддом (Codd E.F.). РМД является наиболее широко распространенной моделью данных и единственной из трёх основных моделей данных, для которой разработан теоретический базис с использованием теории множеств.

Базовой структурой РМД является отношение, основанное на декарто-вом произведении доменов. Домен – это множество значений, которое может принимать элемент данных (например, множество целых чисел, множество дат, множество комбинаций символов длиной N и т.п.). Домен может задаваться перечислением элементов, указанием диапазона значений, функцией и т.д.

Пусть D1, D2 ,…, Dk – произвольные конечные и не обязательно различ-ные множества (домены). Декартово произведение этих множеств определяется следующим образом:

D₁×D₂×...×D_k={(d₁, d₂,...,d_k | d_i  D_i, I=1,...,k)}

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

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