<<
>>

2.3 СЕТЕВАЯ И ИЕРАРХИЧЕСКАЯ МОДЕЛИ ДАННЫХ

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

Сетевая БД представляется как множество отношений и веерных отношений.

Отношения разделяются иа основные и зависимые.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значение отношения при хранении в памяти ЭВМ часто называется записью. Адресом связи называется атрибут в составе записи, в котором хранится начальный адрес или номер следующей обрабатываемой записи.

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

Группа (Код#, Чисяо_студвнтов } Основное отношение

Студент (Номер_зач#, Фамилия) I Зависимое отношение

Значения зависимого отношения Студент а

Склад (Номер#) Изделие (Название») Основные отношения

Значения основного от ношения Изделие б

Остаток (Номер#, Название», Количество) Зависимое отношение

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

Получается кольцевая структура адресов связи, называемая веером, где роль "ручки" веера играет запись основного отношения.

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

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

S(net) = ,

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

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

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

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

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

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

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

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

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

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

F - {F1(X1),F2(X2) Fi(Xi),...,Fn(Xn)},

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

Дополнительно вводится граф сетевой структуры В с вершинами {XI ,X2,...,Xi,...,Xn>.

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

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

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

m(DBA) = F1 & F2 & ... & Fi & ...& Fn, называемая максимальным пересечением. Ее аналогом может служить последовательность соединений в реляционной БД.

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

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

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

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

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

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

F2(Ornen #, НИИ, Ксотр),

F3(TeMa #, Датанач, Датакон, Приор),

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

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

F6(TeMa #, Заказ #, Обфин).

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В результате выполнения двух операторов OBTNM (Сотрудник * "Иванов") ОВТ№(Сотрудник * "Иванов", Зарпл'Осн)

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

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

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

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

Ml: 08ТЫР(Сотрудник * "Иванов", Зарпл *Осн)

print Зарпл

goto М1

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

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

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

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

<< | >>
Источник: Мишенин А. И.. Теория экономических информационных систем: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика. - 240 с. 2002

Еще по теме 2.3 СЕТЕВАЯ И ИЕРАРХИЧЕСКАЯ МОДЕЛИ ДАННЫХ:

  1. ПРЕДИСЛОВИЕ
  2. Предметная область
  3. 2.1 РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ
  4. 2.3 СЕТЕВАЯ И ИЕРАРХИЧЕСКАЯ МОДЕЛИ ДАННЫХ
  5. Иерархическая модель данных
  6. Алгоритм получения структуры иерархической БД 1.
  7. МОДЕЛЬ ИНВЕРТИРОВАННЫХ ФАЙЛОВ И ИНФОРМАЦИОННО-ПОИСКОВЫЕ СИСТЕМЫ
  8. 4.1 СЕМАНТИЧЕСКИЕ МОДЕЛИ ДАННЫХ
  9. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
  10. 1.4. Модели представления данных
  11. 1.4.2 Сетевая модель
  12. 1.4.3. Реляционная модель
  13. § 4.1. Сетевые коммуникации и концепция электронного правительства
  14. 2.1. Креативные ресурсы региональных сообществ
  15. ТЕМА 1. СВОЕОБРАЗНЫЙ ХАРАКТЕР ЦИВИЛИЗАЦИИ РОССИИ
  16. §3. Социальная коммуникация в контексте исследования информационного общества
  17. §1. Сущность процесса трансформации социальности с точки зрения социальной дифференциации