Ранние подходы к реализации БД. Иерархические и сетевые БД

Модель данных иерархическая (Hierarchical Data Model) - это модель данных, в основе которой используется иерархическая древовидная структура данных. Вершинами этой структуры являются записи соответствующего ей типа, называемые также сегментами, состоящие из простых элементов данных различных типов. При этом родительской записи соответствует произвольное число экземпляров подчиненных записей каждого типа. Экземпляр записи каждого типа идентифицируется уникальным ключом, определенным для этого типа. База данных представляет собой совокупность таких деревьев. В модели данных предусматриваются навигационные oперации по структуре базы данных и операция поиска сегмента, в том числе и с использованием иерархического ключа. Поддерживается концепция текущего состояния - вершины дерева структуры данных (в терминах экземпляров, а не типов), достигнутая в результате последней выполненной навигационной операции. Навигационные операции могут использовать идентификацию целевой записи относительно этого текущего состояния. Наряду с навигационными операциями поддерживаются операции манипулирования данными - вставка, обновление и удаление записей с естественным каскадным распро¬странением операции удаления. Иерархическая модель данных активно использовалась во многих СУБД на платформе мейнфреймов до появления реляционных систем. Наи¬более известным ее представителем является модель данных СУБД IMS компании IBM Corp., первая версия которой была разработана в конце 60-х гг. Система IMS эксплуатируется до настоящего времени.
Дерево - это связный неориентированный граф, который не содержит циклов. Обычно при работе с деревом выделяют какую-то конкретную вершину, определяют её как корень дерева и рассматривают особо - в эту вершину не заходит ни одно ребро. В этом случае дерево становится ориентированным. Ориентация определяется от корня. Дерево как ориентированный граф можно определить следующим образом:
• имеется единственная особая вершина, называемая корнем, в которую не заходит ни одно ребро;
• во все остальные вершины заходит только одно ребро, а исходит произвольное количество ребер;
• граф не содержит циклов.
Конечные вершины, то есть вершины, из которых не выходит ни одной дуги, называются листьями дерева.
В иерархических моделях данных используется ориентация древовидной структуры от корня к листьям. Графическая диаграмма схемы базы данных называется деревом определения. Пример иерархической базы данных приведён на рис.

Рис.. Пример иерархической базы данных
Каждая некорневая вершина связана с родительской записью иерархическим групповым отношением. Каждая вершина дерева соответствует сущности ПО, которая характеризуется произвольным количеством атрибутов, связанных с ней отношением 1:1. Атрибуты, связанные с сущностью отношением 1:n, образуют отдельную сущность и переносятся на следующий уровень иерархии. Тип вершины определяется типом сущности и набором её атрибутов. Каждая вершина дерева хранит экземпляры сущностей - записи. Следствием внутренних ограничений иерархической модели является то, что каждому экземпляру зависимой группы в БД соответствует уникальное множество экземпляров родительских групп - по одному экземпляру каждого типа вершин вышестоящих уровней.
В ИМД также предусмотрены специальные способы навигации. Передвижение по дереву всегда начинается с корневой вершины, от которой можно прейти на конкретный экземпляр записи любой вершины следующего уровня. Эта вершина становится текущей вершиной, а экземпляр - текущим экземпляром (записью). От этой записи можно перейти к другой записи данной вершины, к экземпляру записи родительской вершины или к экземпляру записи подчиненной вершины.
Корневая запись дерева должна содержать ключ с уникальным значением. Ключи некорневых записей должны иметь уникальные значения только в экземплярах групповых отношений, т.е. на одном и том же уровне иерархии в разных ветвях дерева могут быть экземпляры записей с одинаковыми ключами. Это объясняется тем, что каждая запись идентифицируется полным сцепленным ключом, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп). Таким образом, попасть в любую вершину можно, только проделав полный путь по дереву от корня.
Связи между записями в ИМД обычно выполнены в виде ссылок (т.е. хранятся адреса связанных записей). Подробнее об этом рассказано в разделе 5.5."Организация связей между хранимыми записями".
Основным недостатком ИМД является дублирование данных. Оно вызвано тем, что каждая сущность (атрибут) может подчиняться (принадлежать) только одной родительской сущности. Таким образом, если надо сохранить, например, данные о детях сотрудника, а на предприятии трудится и отец, и мать ребенка, то информацию о детях придётся хранить дважды. Это может вызвать нарушение логической целостности БД при внесении изменений в данные о детях.
Если данные имеют естественную древовидную структуризацию, то использование иерархической модели данных не вызывает проблем. Но на практике часто требуется реализовать структуры данных, отличные от иерархической. Для решения этих задач конкретные СУБД, основанные на ИМД, включают дополнительные средства, облегчающие представление произвольно организованных данных.
Модель данных сетевая ( Network Data Model ) - это модель, допустимые структуры данных в которой могут быть представлены в виде графа общего вида. Вершинами такого графа могут являться данные различных типов - от атомарных элементов данных до записей сложной структуры. Дуги графа представляют связи между этими данными. Примерами этого класса моделей могут служить модель данных CODASYL, бинарная сеть Ж. Абриаля (J. Abrial) и разработанная М. Сенко (М. Senko) и др. модель DIAM.
Сетевая модель позволяет организовывать БД, структура которых представляется графом общего вида (пример СМД - на рис. 3).

Рис. 3. Пример диаграммы Бахмана для фрагмента БД «Город»
Организация данных в сетевой модели соответствует структуризации данных по версии CODASYL. Каждая вершина графа хранит экземпляры сущностей (записи) и сведения о групповых отношениях с сущностями других типов. Каждая запись может хранить произвольное количество значений атрибутов (элементов данных и агрегатов), соответствующих экземпляру сущности.
Групповые отношения характеризуют следующие признаки:
1. Способ упорядочения подчинённых записей.
Поддерживаются три способа упорядочения:
• Очередь - добавление в конец списка (FIFO - first input, first output).
• Стек - добавление в начало списка (LIFO - last input, first output).
• Сортировка по значению ключа. В этом случае задаётся ключевое поле (поля), и вновь поступившая запись добавляется в упорядоченный список в соответствии со значением этого поля (значением ключа).
2. Режим включения подчинённых записей.
Режим включения бывает автоматический и ручной.
При автоматическом режиме подчиненная запись связана с записью-владельцем обязательной связью, поэтому она включается в групповое отношение и прикрепляется к записи-владельцу в момент внесения в БД. (Из этого следует, что запись-владелец должна быть внесена в БД до внесения первого экземпляра подчиненной записи.)
При ручном режиме включения подчиненная запись может находиться в БД и не быть прикрепленной к записи-владельцу. Она вручную включается в групповое отношение тогда, когда это отношение (связь) возникает.
3. Режим исключения подчинённых записей.
Режим исключения определяется классом членства. Различают три класса членства: фиксированный, обязательный и необязательный. Записи с фиксированным членством удаляются вместе с записью-владельцем. Записи с обязательным членством должны быть удалены до удаления записи-владельца: владелец, к которому прикреплена хотя бы одна запись с обязательным членством, не может быть удален. Записи с необязательным членством при удалении записи-владельца останутся в БД.
В СМД применяются следующие операции над данными:
• запомнить: внесение информации в БД;
• включить в групповое отношение: установление связей между данными;
• переключить: переход члена набора к другому владельцу;
• обновить: модификация данных;
• извлечь: чтение данных;
• удалить: физическое или логическое удаление данных;
• исключить из группового отношения: разрыв связей между данными.
Связи между записями в СМД обычно выполнены в виде указателей (т.е. каждая запись хранит ссылки на другие однотипные записи и записи, связанные с ней групповыми отношениями).
В сетевой модели данных предусмотрены специальные способы навигации и манипулирования данными. Аппарат навигации в графовых моделях служит для установления тех объектов данных, к которым будет применяться очередная операция манипулирования данными. Такие объекты называются текущими. В СМД возможны переходы:
• от текущего экземпляра записи определённого типа к другим экземплярам записи этого же типа;
• из текущей вершины в любую вершину, с которой текущая связана групповым отношением.
Наиболее распространенной и стандартизованной из реализаций СМД является модель CODASYL. В соответствии с ней описание схемы БД осуществляется на языке COBOL, а манипулирование данными - с помощью включающего языка программирования высокого уровня.