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

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

Учебный курс	День занятий	Студент
C1	Понедельник Среда	Иванов Петров Сидоров
C2	Пятница	Мягков Быков

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

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

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

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

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

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

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

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

CDS	Учебный курс	День занятий	Студент
	C1	Понедельник	Иванов
	C1	Понедельник	Петров
	C1	Понедельник	Сидоров
	C1	Среда	Иванов
	C1	Среда	Петров
	C1	Среда	Сидоров
	C2	Пятница	Мягков
	C2	Пятница	Быков

Важно отметить, что для рассматриваемых данных функциональные зависимости, кроме тривиальных, не заданы. Нормализованное отношение 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 (Учебный курс, Студент).

CD	Учебный курс	День занятий		CS	Учебный курс	Студент
	C1	Понедельник			C1	Иванов
	C1	Среда			C1	Петров
	C2	Пятница			C1	Сидоров
					C2	Мягков
					C2	Быков

Оба отношения находятся в НФБК; более того, исходное отношение 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.