5.4. Иерархическая и сетевая модели представления данных
Более сложными моделями по сравнению с файловыми являются иерархические и сетевые модели, которые предполагают, что БД содержит описания совокупности взаимосвязанных объектов [38, 64]. Связь двух объектов отражает их подчиненность.
Иерархическая БД представляет собой древовидную структуру и состоит из упорядоченного набора деревьев (ориентированных графов) или, точнее, упорядоченного набора нескольких деревьев (графов) одного и того же типа. Напомним, что граф — совокупность точек, изображенных на плоскости (верши-
ны графа) и связей между ними в виде линий, соединяющих их (ребра или дуги графа). Вершина, с которой начинается дерево (см. рис. 5.4), называется корневой. Каждая вершина (родительская) может порождать ряд других вершин (потомков), которые располагаются ниже. Графом, например, удобно описывать структуру управления организацией, начиная от ее руководителя и заканчивая конкретным исполнителем.
Тип дерева представляет собой иерархически организованную совокупность, содержащую один корневой тип записи и упорядоченный набор, который может содержать или не содержать множество типов поддеревьев, каждое из которых относится к определенному типу дерева.
Между записями в иерархии могут быть определены связи: один ко многим или один к одному, где запись, соответствующая элементу один, определяется как исходная, а соответствующая элементу много — как порожденная. Для иерархической структуры характерно, что запись-потомок имеет только одного предка, у которого может быть множество потомков. В общем случае данные в иерархической БД могут представляться несколькими деревьями.
В иерархических БД автоматически поддерживается целостность ссылок между предыдущим (родителями) и последующим (потомками). Основное правило — последующее не может существовать без своего предыдущего. Аналогичное поддержание целостности по ссылкам между записями, не входящими в одну иерархию, не поддерживается.
В различных СУБД описание объекта для БД иерархического типа может называться по-разному: тип записи, файл, сегмент (далее используем термин «запись»). В свою очередь, запись состоит из одного или нескольких элементов данных (это аналог поля в файловой модели). Элементы упорядочиваются в некотором порядке.
Записи одной структуры образуют тип записи. Отдельные записи некоторого типа называют экземплярами записи. Модель данных может включать несколько типов записей. При этом запись конкретного типа называют объектом модели.
Между объектами модели данных устанавливаются связи. Они также характеризуются типом. Связи между разными объектами (между парой экземпляров записей разного типа) могут иметь разный тип.
В качестве пояснения ниже приводится концептуальная и логическая модели иерархической БД для «Классификатора таможенных органов и их структурных подразделений». Этот классификатор применяется при подготовке и контроле таможенных документов.
Известно, что в структуре ФТС России выделяют три типа объектных множеств: региональные таможенные управления (РТУ), таможни (Т) и таможенные посты (ТП). Они находятся в линейной подчиненности РТУ-Т-ТП. Описание каждого типа объектов состоит из двух элементов: имя и код, однако они имеют разный смысл. Для объектов типа РТУ — это наименования и коды региональных таможенных управлений, для Т — наименования и коды таможен, для ТП — наименования и коды таможенных постов. Таким образом, концептуальная модель создаваемой базы предполагает задание и сохранение в БД опи-
саний объектов трех типов, находящихся в линейной подчиненности (рис. 5.12).
Конкретная таможня подчиняется только одному РТУ, а ТП — только одной таможне, поэтому для каждого РТУ можно построить дерево подчиненности, в котором у каждого потомка будет только один предок, а корнем дерева будет объект типа РТУ. Следовательно, взаимосвязь данных в создаваемой БД описывается иерархическим деревом, что является особенностью БД иерархического типа. Поскольку в состав каждого РТУ входят несколько таможен, а в таможню — несколько ТП, можно выделить два типа связей: первый — [РТУ—» Т] и второй — [Т -> ТП] (см. рис. 5.12). Поскольку в ФТС России семь РТУ, логическая модель создаваемой БД будет иметь семь однотипных деревьев (рис. 5.13). Количество потомков записей РТУ или Т будет зависеть от структуры соответствующих РТУ. Для описания элементов объектов в логической модели будет три типа записей по числу типов объектов: РТУ, Т и ТП.
Рис. 5.13. Логическая модель БД классификатора
Например, запись типа РТУ, описывающая Центральное таможенное управление (ЦТУ), будет иметь вид:
Дальневосточное таможенное управление состоит из 18 таможен, соответственно в дереве, описывающем это управление, у записи типа РТУ будет
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].