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

В структуру основного и зависимого отношений вводится дополнительный атрибут, называемый адресом связи. Значения адресов связи совместно обеспечивают в веерном отношении соответствие каждого значения зависимого отношения 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,

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

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

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