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

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

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

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

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

Связь (англ. link) — иерархическое отношение между записями двух типов; некоторые авторы по аналогии с сетевой моделью пользуются термином «групповое отношение». Связи при графическом изображении обозначаются дугами ориентированного графа, типы записей — вершинами. Такое изображение структуры БД называется диаграммой Бахмана (автор — американский исследователь Ч. Бахман (Charles Bachman), один из пионеров в области баз данных, получивший за свои работы в 1973 г. премию Тьюринга). Дуги графа, обозначающие логические связи, являются направленными. Запись, из которой выходит стрелка, является логически исходной; запись, в которую приходит стрелка, — логически подчиненной.

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

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

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

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

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

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

Рис. 3.1. Иерархические базы данных:

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

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

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

• • операция добавить (INSERT) позволяет занести в БД новую запись (с учетом ограничений, связанных с требованиями относительно уникальности ключа в рамках всей БД для корневой записи и среди «близнецов» — для подчиненной);
• • операция обновить (UPDATE) дает возможность изменить значения данных предварительно извлеченной записи. Ключевые данные записи не могут подвергаться обновлению, в подобных случаях старая запись должна быть удалена, а новая, содержащая измененные данные, — запомнена;
• • операция удалить (DELETE) служит для исключения из БД некоторой записи и всех подчиненных ей;
• • операция извлечь (GET) имеет несколько модификаций — извлечь по значению ключа, извлечь следующую запись (в порядке левостороннего обхода дерева), извлечь следующую, удовлетворяющую дополнительному условию и т. д.

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