<< Вернуться у выбору материала

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

Введите ваш запрос для начала поиска.

http://plakatmsk.ru/ нужный каждому ученику плакат делай уроки.

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

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

На рис. 3.8 изображена сетевая структура базы данных в виде графа.

Графическое изображение сетевой структуры

Рис. 3.8 Графическое изображение сетевой структуры

Примером сложной сетевой структуры может служить структура базы данных, содержащей сведения о студентах, участвующих в научно-исследовательских работах (НИРС). Возможно участие одного студента в нескольких НИРС, а также участие нескольких студентов в разработке одной НИРС. Графическое изображение описанной в примере сетевой структуры, состоящей только из двух типов записей, показано на рис. 3.9. Единственное отношение представляет собой связь между записями в обоих направлениях.

Пример сетевой структуры БД

Рис. 3.9 Пример сетевой структуры БД

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

Веерным отношением W(R,S) называется пара отношений, состоящая из одного основного R, одного зависимого отношения S и связи между ними при условии, что каждое значение зависимого отношения связано с единственным значением основного отношения.

Названное условие является ограничением, характерным для сетевой модели данных в целом. Способ реализации этого ограничения в памяти ЭВМ неодинаков у различных сетевых СУБД.

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

Сетевые базы данных в зависимости от ограничений на вхождение отношений в веерные отношения разделяются на многоуровневые сети и двухуровневые сети.

Ограничение двухуровневых сетей состоит в том, что каждое отношение может существовать в одной из перечисленных ниже ролей:

• вне каких-либо веерных отношении,

• в качестве основного отношения в любом количестве веерных отношений,

• в качестве зависимого отношения в любом количестве веерных отношений;

Запрещается существование отношения в качестве основного в одном контексте и одновременно в качестве зависимого в другом контексте.

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

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

Для двухуровневых сетевых СУБД вводятся еще два ограничения (с теоретической точки зрения необязательные):

• первичный ключ основного отношения может быть только одно-атрибутным,

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

Организация веерного отношения в памяти ЭВМ

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

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

Получается кольцевая структура адресов связи, называемая веером, где роль "ручки" веера играет запись основного отношения. На графических иллюстрациях адрес связи изображается стрелкой, направленной от адреса связи данной записи к той записи, чей начальный адрес (номер) служит значением этого адреса связи. На рис. 2.2 показаны структуры и значения веерных отношений двух простых сетевых двухуровневых БД. Атрибуты первичного ключа во всех случаях помечены #.

Схема сетевой БД содержит следующие компоненты:

S(net) = <A,R,WW,Dom,Rel,Net,V(s)>,

где WW - множество веерных отношений,

Net - вхождение отношений в веерные отношения.

Остальные элементы схемы аналогичны тем, которые введены выше для реляционных баз данных.

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

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

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

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

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

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

В схеме сетевой БД отношения и веерные отношения часто трактуются как файлы и связи, что позволяет рассматривать сетевую структуру как множество файлов

F = {Fl(Xl),F2(X2),...,Fi(Xi),...,Fn(Xn)},

где Xi - атрибуты ключа в файле Fi.

Дополнительно вводится граф сетевой структуры В с вершинами {Xl,X2,...,Xi,...,Xn}. Дуга <Xi,Xj> в графе В существует, если Xi является частью Xj и Fj[Xi] является подмножеством Fi. Последнее условие имеет тот же смысл, что и синтаксическое включение отношений в реляционной модели данных. Здесь предполагается, что ключ основного файла содержится в зависимом файле. Граф В аналогичен графу соединений для реляционной БД.

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

Для множества файлов F ациклической базы данных DBA вполне применима операция

m(DBA) = F1 & F2 & ... & Fi & ...& Fn,

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

Рассмотрим алгоритм формирования структуры двухуровневой сетевой БД на основе известного множества атрибутов и функциональных зависимостей.

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

Алгоритм получения двухуровневой структуры сети

1. Для каждой функциональной зависимости вида А ® В создается файл Fi(A,B). Каждый блок взаимно однозначных соответствий также порождает файл с ключом, равным старшему по объему понятия атрибуту.

В нашем примере будут созданы следующие файлы (ключи помечены знаком #):

F1(НИИ #, Директор, Адрес),

F2(0тдел #, НИИ, Ксотр),

FЗ(Тема #, Датанач, Датакон, Приор),

F4(ФИО #, Отдел),

F5(Тема #, Работа #, ФИО #, Прод),

F6(Тема #, Заказ #, Обфин).

2. У всех пар файлов, полученных на шаге 1, проверяется условие для ключей (Ki является частью Kj). Если оно соблюдается, то из соответствующих файлов создается веерное отношение Wij(Fi,Fj).

В нашем примере получим W35(F3,F5), W45(F4,F5), W36(F3,F6).

3. Если на шаге 2 будут получены два веерных отношения Wij и Wjk, то все атрибуты файла Fi передаются в файл Fj, и Fi вместе с Wij уничтожаются.

В нашем примере таких веерных отношений нет.

4. Атрибуты, не вошедшие в состав веерных отношений на шаге 2, добавляются в те файлы Fn (и содержащие Fn веерные отношения), где они будут не ключевыми. При наличии нескольких подходящих файлов предпочтение отдается основным файлам. Если требуемые Fn отсутствуют, то создается новый файл из атрибутов первичного ключа, и повторяются шаги 2, 3,4.

В нашем примере F4 расширяется атрибутами НИИ, Директор, Адрес, Ксотр.

На рис. 3.10 показана структура соответствующей двухуровневой БД.

Сетевая БД со сведениями о научно-исследовательских работах

Рис. 3.10 Сетевая БД со сведениями о научно-исследовательских работах

Структуры основных отношений показаны в верхней части рисунка, а структуры зависимых отношений - внизу.

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

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

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

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

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

Пример сетевой БД для операций выборки

Рис. 3.11 Пример сетевой БД для операций выборки

1. Операция OBTNM - получить запись в основном отношении.

OBTNM (Сотрудник * "Иванов")

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

2. Операция OBTNF - получить запись в зависимом отношении.

OBTNF(Сотрудник * "Иванов", Зарпл*0сн)

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

В результате выполнения двух операторов

OBTNM (Сотрудник * "Иванов")

ОВТМР(Сотрудник * "Иванов", Зарпл*0сн)

при условии, что обращения к отношению Зарпл ранее не производились, будут получены сведения о первой (с момента поступления на работу) основной зарплате Иванова.

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

Рассмотрим, например, последовательность операций

OBTNM (Сотрудник * "Иванов")

Ml: OBTNF(Сотрудник * "Иванов", Зарпл*0сн)

print Зарпл

goto Ml

Оператор print печатает все атрибуты текущей записи отношения Зарпл. На первый взгляд использование безусловного перехода создает зацикливание при выполнении. Однако операторы выборки в сетевых СУБД по окончании выборки вырабатывают код возврата, и выход за последнюю запись в отношении Зарпл сопровождается специальным значением этого кода в команде OBTNF, означающим неудачное завершение выборки. Значение кода возврата всегда проверяется средствами включающего языка, и этим обеспечивается выход из цикла. Практически приведенная выше последовательность операций напечатает все сведения о получении Ивановым основной заработной платы.

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

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

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

Отображение информационной схемы на сетевую модель данных

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

Например, на этапе концептуального проектирования получена информационная схема, изображенная на рис. 3.12

Информационная схема

Рис. 3.12 Информационная схема

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

Рис. 3.13 Сетевая модель данных

Обозначение М1 / N1, читается так: N1 изделий выполняется М1инструментами, М1/ М2 читается так: М1 инструмент используется на М2рабочих местах.

Определенная аналитическая работа требуется при привязке сетевой модели к конкретной СУБД.

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

В приведенном выше примере (см.рис. 3.12, 3.13) основные файлы: изделие, инструмент, рабочее место, технологическая операция. Для связи между ними введем вспомогательный файл связей, тогда логическая схема БД, ориентированная на СУБД СЕТОР, будет иметь вид, показанный на рис. 3.14 (вспомогательный файл обозначен двойной линией). Легко понять состав полей вспомогательного файла: номер изделия, номер инструмента, номер рабочего места, номер технологической операции.

Рис. 3.14 Логическая схема

Рейтинг@Mail.ru