Вопрос 32. сетевые и иерархические модели данных. Структура данных.

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

 

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

 

К типовым структурам данных относятся: элемент данных, агрегат данных, запись, база данных и т. д.

 

Элемент данных -- это минимальная именованная структурная единица данных (аналог поля в файловых системах).

 

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

 

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

 

Связи между двумя типами записей (объектами модели) определяются групповыми отношениями между их экземплярами. Групповое отношение (набор) -- это строго иерархическое отношение между записями двух типов: главной записью набора и подчиненными записями набора.

 

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

 

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

 

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

 

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

 

 

етевая модель

Сетевая модель относится к ранним моделям данных. Сейчас информации об этой модели данных почти не встретишь, даже такой специалист как К. Дейт при переиздании своей классической книги «Введение в системы баз данных» исключил вопросы, касающиеся сетевой и иерархической модели данных (см. [8] и [15]). Впрочем, в последнее время снова заговорили о сетевой модели в связи с распределенными информационными системами, а также с развитием объектных моделей данных.

В 1971 группа DTBG (Database Task Group) представила в американский национальный институт стандартов отчет, который послужил в дальнейшем основой для разработки сетевых систем управления базами данных. Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия модели и формальный язык описания.

Сетевая модель данных опирается на математическую теорию направленных графов. Базовыми элементами сетевой модели являются:

· Элемент данных – минимальная информационная единица доступная пользователю.

· Агрегат данных – именованная совокупность элементов данных внутри записи или другого агрегата. Агрегат бывает двух видов – агрегат типа вектор и агрегат типа повторяющаяся группа. Например, агрегат <город, улица, дом, квартира>, которому можно присвоить имя Адрес, является агрегатом типа вектор. Примером, агрегата типа повторяющаяся группа может служить агрегат <месяц, сумма> с названием Зарплата. Агрегат повторяющаяся группа характеризуется числом повторений. В данном примере это число повторений равно 12.

· Запись - совокупность агрегатов или элементов данных, отражающих некоторую сущность предметной области. Например, записью будет <Фамилия, Зарплата>, где Фамилия – это элемент данных, а Зарплата – агрегат. Данную запись можно назвать Зарплата сотрудника.

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

· Набор - именованная двухуровневая иерархическая структура, которая содержит запись владельца и запись (или записи) членов. Наборы отражают связи «один ко многим» и «один к одному» между двумя типами записей. На рисунке 2.5 представлен пример набора. Здесь Отдел – запись–владелец, сотрудник - запись-член. Тип набора определяет связь между двумя типами записей. Каждый экземпляр типа набора содержит один экземпляр записи владельца и произвольное количество записей-членов (для связи типа «один ко многим»). Обратите внимание, как на рисунке 2.5 обозначается связь «один ко многим». Разветвление на конце указывает на множество экземпляров некоторого объекта. Такой способ обозначения связей мы будем использовать и далее. Среди всех наборов в сетевой модели допускается существование наборов, не имеющих владельцев. Такие наборы называются сингулярными. Владельцами сингулярных наборов формально считается система. Сингулярные наборы предназначены для доступа к экземплярам отдельных записей.

Рис. 2.5. Набор в сетевой модели данных

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

Отметим некоторые особенности построения сетевой модели.

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

· Связь между двумя записями может выражаться произвольным количеством наборов.

· В любом наборе может быть только один владелец.

· Тип записи может быть владельцем в одних типах наборов и членом в других типах наборов.

· Тип записи может не входить ни в какой тип наборов.

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

· Язык описания данных в сетевой модели.

o Описание базы данных (размещение).

o Описание элементов, агрегатов и записей.

o Описание наборов.

· Язык манипулирования данными.

o Навигационные операции. С помощью операций навигации (группа операций FIND) двигаясь по связям можно переходить от одной текущей записи к другой. Соответственно операции модификации осуществляются над текущей записью.

o Операции модификации. Операции модификации осуществляют:

§ Добавление новых экземпляров отдельных типов записей.

§ Экземпляров новых наборов.

§ Удаление экземпляров записей и наборов.

§ Модификацию отдельных составляющих внутри конкретных экземпляров записей.

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

Исторически иерархическая модель появилась раньше сетевой. Она наиболее проста из всех моделей данных. Самой известной иерархической системой позволяющей создавать иерархические базы данных является система IMS (Information Management System) фирмы IBM, используемая в свое время для поддержки лунного проекта «Аполлон». Появление иерархической модели связано с тем, что в реальном мире очень многие связи соответствуют иерархии, когда один объект выступает как родительский, а с ним может быть связано множество подчиненных объектов.

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

На рисунке 2.6 схематически представлена иерархическая структура. Узлы (сегменты) соединены друг с другом связующими дугами. Сегмент A является корневым сегментом. Сегменты B, E, H, J, I являются листовыми сегментами. Каждый сегмент, при этом, может содержать произвольное количество полей.

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

Рис. 2.6. Иерархическая структура

Иерархическая модель довольно удобна для представления предметных областей, так как иерархические отношения довольно часто встречаются между сущностями реального мира. Но иерархическая модель не поддерживает отношения «многие ко многим», когда множество объектов одного типа связаны с множеством объектов другого типа. Предположим, что требуется построить модель отношения между множеством собственников жилья и множеством квартир. Если основной вопрос будет заключаться в определении того, каким жильем владеет тот или иной собственник, то естественно взять в качестве родительских узлов данные о собственнике. При этом каждый сегмент - собственник будет связан с N узлами – квартирами. Таким образом, по собственнику мы легко найдем все квартиры, которые находятся в его собственности. Однако проблема заключается в том, что у одной и той же квартиры может быть несколько собственников. Т.е. одна и та же квартира может встречаться в разных деревьях. В результате решения таких задач, как получение списка всех квартир, или получения всех собственников конкретной квартиры, будут уже не столь очевидными. Кроме того, сложной выглядит даже операция удаления из базы конкретной квартиры, поскольку для этого придется просматривать все деревья. Можно, конечно, построить параллельно деревья, в которых родительскими сегментами будут данные о квартирах, а порождаемыми сегментами – данные о владельцах, но в результате мы получим еще избыточность данных, что породит дополнительную проблему их согласованности.

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