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

Рассмотрим некоторое ненормализованное отношение, задающее расписание занятий:

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

Предположения, которые могут быть сделаны:

1. Каждый курс может иметь произвольное количество дней занятий.

2. Каждый курс могут изучать произвольное количество студентов.

3. Дни занятий и студенты совершенно не зависят друг от друга, т.е. независимо от дня занятий состав группы студентов один и тот же.

4. День занятий может быть связан с любыми курсами.

5. Каждый студент может быть связан с любым курсом.

Преобразуем данное отношение в нормализованное отношение CDS:

Важно отметить, что для рассматриваемых данных функциональные зависимости, кроме тривиальных, не заданы. Нормализованное отношение CDS означает, что кортеж

<Учебный курс:c, День занятий:d, Студент:s>

появляется в отношении тогда и только тогда, когда занятия по курсу c проводятся в день недели d и посещаются студентом s.

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

Если в отношении существуют кортежи <c, d1, s1> и <c, d2, s2>, то также присутствуют и кортежи <c, d2, s1> и <c, d1, s2>.

Очевидно, что в данном отношении имеет место избыточность, которая может привести к проблемам.

Проблема вставки. Чтобы добавить в приведенное отношение информацию о том, что занятия по курсу C2 могут проводиться еще и в четверг, надо включить в отношение два кортежа: <C2, четверг, Мягков> и <C2, четверг, Быков>.

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

Проблема удаления. Чтобы отменить, например, занятия в понедельник по курсу C1, надо удалить из отношения три кортежа.

Тем не менее, отношение CDS находится в НФБК, так как все атрибуты отношения образуют первичный ключ.

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

CD(Учебнвый курс, День занятий) и CS (Учебный курс, Студент).

Оба отношения находятся в НФБК; более того, исходное отношение CDS может быть восстановлено с помощью операции естественного соединения отношений CD и CS, т.е. выполнена декомпозиция без потери информации, но эта декомпозиция выполнена не на основе функциональной зависимости.

Эти интуитивные идеи были теоретически сформулированы Фейгином (Fagin) в 1971 г. с помощью понятия многозначных зависимостей. Приведенная выше декомпозиция выполняется на основе многозначных зависимостей.

Определение

Пусть A, B, C – некоторое произвольное подмножество атрибутов схемы отношения R(A, B, C). Тогда B многозначно зависит от A (A ®® B) тогда и только тогда, когда множество значений B, соответствующее заданной паре <A:a, C:c> отношения R зависит только от A, но не зависит от C.

Фейгин показал, что для данного отношения R(A, B, C) многозначная зависимость A ®® B выполняется тогда и только тогда, когда также выполняется многозначная зависимость A ®® C.

Таким образом, многозначные зависимости всегда образуют пары: A ®® B | C.

В нашем примере имеет место многозначная зависимость:

Учебный курс ®® День занятий | Студент

Всякая функциональная зависимость является многозначной, но не всякая многозначная зависимость является функциональной. Фейгин сформулировал следующую теорему.

Теорема

Пусть A, B, C – некоторые множества атрибутов схемы отношения R(A, B, C). Отношение R будет равно соединению его проекций R₁(A, B) и R₂(A, C) тогда и только тогда, когда для отношения R выполняется многозначная зависимость A ®® B.