5.4. Иерархическая и сетевая модели представления данных

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

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

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

274

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

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

Между записями в иерархии могут быть определены связи: один ко многим или один к одному, где запись, соответствующая элементу один, определяется как исходная, а соответствующая элементу много — как порожденная. Для иерар­хической структуры характерно, что запись-потомок имеет только одного пред­ка, у которого может быть множество потомков. В общем случае данные в иерар­хической БД могут представляться несколькими деревьями.

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

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

Записи одной структуры образуют тип записи. Отдельные записи некоторого типа называют экземплярами записи. Модель данных может включать несколько типов записей. При этом запись конкретного типа называют объектом модели.

Между объектами модели данных устанавливаются связи. Они также харак­теризуются типом. Связи между разными объектами (между парой экземпляров записей разного типа) могут иметь разный тип.

В качестве пояснения ниже приводится концептуальная и логическая моде­ли иерархической БД для «Классификатора таможенных органов и их структур­ных подразделений». Этот классификатор применяется при подготовке и конт­роле таможенных документов.

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

275

саний объектов трех типов, находящихся в линейной подчиненности (рис. 5.12).

Конкретная таможня подчиняется только одному РТУ, а ТП - только одной таможне, поэтому для каждого РТУ мож­но построить дерево подчиненности, в котором у каждого потомка будет толь­ко один предок, а корнем дерева будет объект типа РТУ. Следовательно, взаимо­связь данных в создаваемой БД описыва­ется иерархическим деревом, что является особенностью БД иерархического типа. Поскольку в состав каждого РТУ входят несколько таможен, а в тамож­ню - несколько ТП, можно выделить два типа связей: первый - [РТУ—» Т] и второй - [Т -> ТП] (см. рис. 5.12). Поскольку в ФТС России семь РТУ, логи­ческая модель создаваемой БД будет иметь семь однотипных деревьев (рис. 5.13). Количество потомков записей РТУ или Т будет зависеть от структуры соответ­ствующих РТУ. Для описания элементов объектов в логической модели будет три типа записей по числу типов объектов: РТУ, Т и ТП.

Рис. 5.13. Логическая модель БД классификатора

Например, запись типа РТУ, описывающая Центральное таможенное управ­ление (ЦТУ), будет иметь вид:

Дальневосточное таможенное управление состоит из 18 таможен, соот­ветственно в дереве, описывающем это управление, у записи типа РТУ будет

276

18 записей-потомков. Конкретная таможня, например Владивостокская, будет представлена записью:

Имя Код

В СУБД на основе иерархической модели типичными являются операции типа:

• найти указанное дерево БД;

• найти указанный экземпляр записи в ранее выбранном дереве;

• просмотреть записи некоторого типа в заданном порядке; -добавить запись в заданную позицию иерархии и др.

В пункте 5.1 указывалось, что для хранения в памяти ЭВМ иерархической структуры данных используется система указателей. Поэтому, например, при размещении в память ЭВМ записи типа РТУ после нее будет к ячеек-указате-лей с адресами расположения записей типа Т (к - число таможен, подчиненных определенному РТУ). В конце каждой записи типа Т будет столько указателей, сколько таможенных постов у соответствующей таможни.

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

Для выбора информации из иерархической БД надо последовательно задать несколько ключей. Так, для выбора информации о некоторой таможне в рассмот­ренной выше БД надо сначала задать ключ выбора таможенного управления, а затем - ключ выбора таможни.

В технической литературе в качестве примеров иерархических БД часто называют системы IMS (Information Management System), TDMS (Time-Shared Data Management System), Mark IV (Multi-Access Retrieval System), System-2000 и др. [38, 64].

Сетевая модель данных

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

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

277

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

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

Владельцы товаров Брокеры

Достаточно очевидно, что в этой БД будет четыре типа записей: < Владелец товара>, <Брокер>, <Грузовая таможенная декларация^ <Вид товара>.

Логическую структуру сетевой БД можно представить в виде графа (рис. 5.15). Нетрудно заметить, что в нем несколько корневых вершин, причем некоторые из них имеют нескольких предков, что является характерным свойством сетевой модели.

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

Грузовая таможенная декларация

Вид товара

Рис. 5.15. Граф, соответствующий примеру па рис. 5.14.

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

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

278

В СУБД на основе сетевой модели типичными являются операции:

• поиск указанной записи;

• переход от предка к потомку;

• переход от потомка к предку;

• просмотр предков или потомков в заданном порядке;

• добавление записи в заданную позицию иерархии и др.

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

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

Внутримашинное представление данных в сетевой БД, как и в иерархичес­кой, предполагает снабжение записей указателями.

В технической литературе в качестве примеров сетевых БД часто называют системы IDS (Integrated Data Store), IDMS (Integrated Database Management System), db. VISTA и др. [38, 64].