Ациклические базы данных

Тема 6

Лекция № 6

Ациклические базы данных

1. Многозначные зависимости.

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

В отношении R(A,B,C) имеется многозначная зависимость А —>—» В, если для любого а, являющегося значением реквизита А

где- множество значений реквизита В, связанных с заданным значением реквизита в; 0 - знак декартова произведения множеств.

Положение реквизитов В к С равноценно, поэтому одновременно справедливо А -»—> С, т. е. многозначные зависимости всегда встречаются парами.

Отношение R (А, В, С) с многозначной зависимостью А —»—> В содержит избыточную информацию, хотя и несколько другого рода, чем отношение в 1НФ. Оказывается, что отношения R1=R[A, В] и R=R2[A,C] вместе представляют всю информацию из R. Справедливо соотношение R=R1*R2, которое можно считать равноценным определению многозначной зависимости.

Рассмотрим отношение Е(3авод, Изделие, Компл, План), где Компл - название комплектующего изделия для данного Изделия, а План - план выпуска Изделий. Справедлива функциональная зависимость Завод, Изделие —> План и мы имеем следующие отношения в ЗНФ:

Z1 (Завод, Изделие, План),

Z2(3aвод, Изделие, Компл).

Отношение Z1 содержит двухреквизитный ключ и в нем не может быть многозначной зависимости. В Z2 существует А/3 вида Изделие —»—> Завод (и, следовательно, Изделие —>—> Компл), поскольку каждое изделие комплектуется одним и тем же набором комплектующих изделий, на каком бы заводе оно ни производилось. Отношение Z2 необходимо разделить на два отношения. Z11 (Завод, Изделие) и Z12(Изделие, Компл). Вся информация из Z11 содержится в Z1, поэтому окончательный список отношений состоит из Z1 и Z12.

Операция соединения позволяет получить Z2 = Z11*Z12.

2. Определение ациклических баз данных.

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

Для определения понятия «ациклическая схема базы данных» введем граф соединений на множестве отношений {S1,S2,...,Sk}. Вершинами графа соединений являются имена отношений 51, S2,...,Sk. Дуга графа <Si,Sj> существует, если в структуре отношений Si и Sj имеются общие реквизиты. Обозначим их через А (i,j) и назовем весом дуги. Путь на графе соединений называется А-путем, если реквизит А содержится в структуре каждого отношения, лежащего на пути. В графе соединений требуется, чтобы для каждой пары отношений Si, Sj с общим реквизитом A (i,j) существовал А (i,j)-путъ между Si и Sj. Если граф можно превратить в дерево с помощью исключения некоторых дуг при сохранении названного требования, то база данных с отношениями {S1, S2,..., Sk:} является ациклической.

Например, в графе соединений на рис. 2.1 можно разорвать любую из дуг и превратить граф в дерево. По этой причине база данных, состоящая из отношений S 1, S 2, S 3, является ациклической.

3. Алгоритм проверки структуры БД на ацикличность

Исходные данные - список отношений с указанием реквизитного состава каждого отношения.

Метод - последовательное выполнение указанных ниже шагов.

Шаг 1. Если некоторый реквизит встречается только в одном отношении, то необходимо вычеркнуть данный реквизит из этого отношения.

Ш а г 2. Если все реквизиты некоторого отношения находятся среди реквизитов другого отношения, то первое отношение вычеркивается из списка.

Шаги 1 и 2 можно применять в любой последовательности.

Если в результате будут вычеркнуты все отношения, то база данных является ациклической. Если будут вычеркнуты не все отношения - база данных циклическая.

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

Рассмотрим простой пример графа соединений (рис. 2.2).

Наличие цикла очевидно. Отношение Т(Служащий, Отдел, Заказчик) может быть вычислено либо как Т= R1 * R2, либо в виде:

T=(R1* R3)[Служащий, Отдел, Заказчик].

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

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

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

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

• При структуре функциональных зависимостей вида А —> В —> С, А —» Е —» С необходимо установить две разные роли для реквизита С (например, С1 и С2). Рассмотрим БД с реквизитами Студент, Группа, Куратор, Кафедра и зависимостями Студент —> Группа -» Кафедра, Студент —> Куратор -> Кафедра. В первом случае подразумевается скорее всего выпускающая кафедра для группы студентов, а во втором - кафедра, на которой работает куратор. После разделения реквизита Кафедра получаем структуру БД в виде:

Р1(Студент, Группа),

Р2(Группа, Выпускающая_кафедра),

РЗ(Студент, Куратор),

Р4(Куратор, Кафедра_куратора).

• Каждое применение теоремы Т6 свидетельствует о цикличности базы данных. Рассмотрим, например, зависимости Служащий —> Отдел и Отдел, Заказчик —» Тема. Эта ситуация отражена на рис. 2.2. Для преодоления цикличности необходимо разделить роли реквизита Отдел, например, ввести реквизит Отдел_служащего.

• Структура функциональных зависимостей вида АВ —> С, С —» В обычно возникает, если действия, совершаемые объектом, приписываются классу объектов. В таком случае необходимо добавить в структуру базы данных реквизит, обозначающий этот объект. Например, служащий фирмы покупает билет в аэропорту и счет направляется в отделение фирмы. Поэтому справедливы зависимости Аэропорт, Фирма —> Отделение и Отделение —» Фирма. Добавив реквизит Служащий, мы разрушаем нежелательную структуру функциональных зависимостей и получаем - Аэропорт, Служащий -> Отделение и Отделение -» Фирма.

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

• каждый входной документ привести к ЗНФ и установить первичный ключ в каждом случае;

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

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