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

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

В отношении R(A,B,C) существует многозначная зависимость (МЗ) АВ, если для любого а, являющегося значением атрибута А

im(BC)a = im(B)a ° im(C)a, где ° - знак декартова произведения множеств.

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

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

Пример

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

Z1 (Завод, Изделие, План), Z2(3авод, Изделие, Компл).

Отношение Z1 содержит двухатрибутный ключ, и в нем не может быть многозначной зависимости. В Z2 существует МЗ вида ИзделиеЗавод (и, следовательно. ИзделиеКомпл), поскольку каждое изделие комплектуется одним и тем же набором комплектующих изделий, на каком бы заводе оно ни производилось. Поэтому Z2 необходимо разделить на два отношения Z21 (Завод, Изделие) и Z22(Изделие, Компл). Вся информация из Z21 содержится в Z1, поэтому окончательный список отношений состоит из Z1 и Z22.

Операция соединения позволяет получить Z=Z1*Z22.

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

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

Если граф можно превратить в дерево с помощью исключения некоторых дуг при сохранении названного требования, то база данных с отношениями {Sl,S2,...,Sk} является ациклической.

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

Рис. 2.1. Пример графа соединений:

а, б - ациклический; в - циклический

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

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

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

Метод

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

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

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

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

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

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

Рассмотрим структуру реляционной базы данных в 3НФ, полученную в предыдущем пункте.

R1(НИИ#, Директор, Адрес), R2(НИИ, Отдел#, Ксотр), RЗ(Тема#, Датанач, Датакон, Приор), R4(ФИО#, Отдел), R5(Тема#, Заказ#, Обфин), R6(Тема#, Работа#, ФИО#, Прод), R7(Тема#, Заказ#, Работа#, ФИО#).

В схемах отношений атрибуты ключа отмечены знаком #. Отношения R1 и R2 имеют одно-атрибутный ключ, ключи остальных отношений являются частью ключа БД из R7, следовательно, эта БД ациклическая. Дерево соединений приводится на рис. 2.1.б.

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

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

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

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

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

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

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

Приведем типичные варианты разделения и переименования атрибутов.

1. При структуре функциональных зависимостей вида АВС, АЕС необходимо установить две различные роли для атрибута С (например, С1 и С2).

Рассмотрим БД с атрибутами Студент, Группа, Куратор, Кафедра и зависимостями СтудентГруппаКафедра, СтудентКураторКафедра. В первом случае подразумевается скорее всего выпускающая кафедра для группы студентов, а во втором - кафедра, на которой работает куратор. После разделения атрибута Кафедра получаем структуру БД в виде:

Р1(Студент, Группа), Р2(Группа, Выпускающая_кафедра), РЗ(Студент, Куратор), Р4(Куратор, Кафедра_куратора).

2. Каждое применение теоремы псевдотранзитивности Тб свидетельствует о цикличности БД.

Рассмотрим, например, зависимости СлужащийОтдел и Отдел, ЗаказчикТема. Это ситуация, показанная на рис.2.1,в. Для преодоления цикличности необходимо разделить роли атрибута Отдел, например, ввести атрибут Отдел_служащего.

3. Структура функциональных зависимостей вида АВС, СВ часто получается, если действия, совершаемые объектом, приписываются классу объектов. Необходимо в таком случае добавить в структуру БД атрибут, обозначающий этот объект.

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

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

Учитывая безусловно высокую трудоемкость приведения отношений к 3НФ при достаточно большом числе атрибутов (в качестве границы можно назвать 12-14 атрибутов), можно рекомендовать следующие действия при проектировании структуры реляционной БД:

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

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

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