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

Занятие №7

Теоретико-графовые модели данных

Теоретико-графовые модели отражают совокупность объектов реального мира в виде графа взаимосвязанных информационных объектов.

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

Однако до сих пор существуют системы, работающие на основе этих моделей.

Концепция   объектно-ориентированных баз данных предполагает  объединение  принципов сетевой модели с концепцией реляционной.

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

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

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

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

  Поле  данных определяется как минимальная, неделимая  единица  данных, доступная пользователю с помощью  СУБД.

• Сегмент  в терминологии Американской Ассоциации по базам данных DBTG ( Data   Base  Task  Group ) называется  записью , при этом в рамках иерархической модели определяются два понятия:  тип сегмента   или  тип записи   и  экземпляр сегмента   или  экземпляр записи .
• Тип сегмента —  это поименованная совокупность типов элементов данных, в него входящих. 
• Экземпляр сегмента  образуется из конкретных значений полей или элементов данных, в него входящих.

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

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

Ключом называется набор элементов данных, однозначно идентифицирующих экземпляр сегмента.

В иерархической модели   сегменты  объединяются в ориентированный древовидный  граф .

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

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

Иногда исходные  сегменты  называют сегментами-предками , а подчиненные  сегменты  называют сегментами-потомками

Пример иерархической связи между сегментами

На концептуальном уровне определяется понятие схемы  БД  в терминологии иерархической модели.

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

Каждая физическая  БД  удовлетворяет следующим иерархическим ограничениям:

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

Существует различие между сегментом и типом сегмента — оно такое же, как между типом переменной и самой переменной: сегмент является экземпляром типа сегмента . 

Между экземплярами сегментов также существуют иерархические связи. Рассмотрим, например, иерархический  граф , представленный на рисунке

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

На рисунке ниже представлены 2 экземпляра иерархического дерева соответствующей структуры

Экземпляры-потомки одного типа, связанные с одним экземпляром сегмента-предка , называют " близнецами ". Так, для нашего примера экземпляры b1, b2 и b3 являются "близнецами", но экземпляр b4 подчинен другому экземпляру родительского сегмента, и он не является "близнецом" по отношению к экземплярам b1, b2 и b3. Набор всех экземпляров сегментов , подчиненных одному экземпляру корневого сегмента, называется  физической записью . Количество экземпляров-потомков может быть разным для разных экземпляров родительских сегментов, поэтому в общем случае физические записи имеют разную длину. Так, используя принцип линейной записи иерархических графов можно представить данный пример с рисунка в виде двух записей:

• В рамках иерархической модели выделяют языковые средства описания данных ( DDL ,  Data Definition Language ) и средства манипулирования данными ( DML ,  Data Manipulation Language ).
• Каждая физическая база описывается набором операторов, определяющих как ее логическую структуру, так и  структуру хранения БД .

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

Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL.

Базовыми объектами модели являются: элемент данных; агрегат данных; запись; набор данных.

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

Агрегат данных   соответствует следующему уровню обобщения в модели. В модели определены агрегаты двух типов: агрегат типа вектор   и агрегат типа  повторяющаяся группа .

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

Адрес

  Город Улица Дом Квартира

Агрегат типа повторяющаяся  группа  соответствует совокупности векторов данных. Например, агрегат  Зарплата  соответствует типу повторяющаяся  группа  с числом повторений 12.

Зарплата

Месяц Сумма

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

Следующим базовым понятием в сетевой модели является понятие "Набор". Набором называется двухуровневый  граф , связывающий отношением " один-ко-многим " два типа записи.

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

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

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

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

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

Например, можно построить два взаимосвязанных набора. Существенным ограничением набора является то, что один и тот же  тип записи  не может быть одновременно владельцем и членом набора.

Рассмотрим таблицу, на основе которой организуем два набора и определим  связь  между ними

Экземпляров набора  Ведет занятия  будет 3 (по числу преподавателей), экземпляров набора  Занимается у  будет 4 (по числу групп). На рисунке представлены взаимосвязи экземпляров данных наборов.

Среди всех наборов выделяют специальный тип набора, называемый " Сингулярным набором ", владельцем которого формально определена вся система. Сингулярный набор изображается в виде входящей стрелки, которая имеет собственно имя набора и имя члена набора, но у которой не определен  тип записи  "Владелец набора". Например, сингулярный набор М.

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

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

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

Язык описания данных в сетевой модели имеет несколько разделов:

• описание базы данных — области размещения;
• описания записей — элементов и агрегатов (каждого в отдельности);
• описания наборов (каждого в отдельности).

Язык манипулирования данными в сетевой модели

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