Базы данных. Вводный курс


Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма


Заметим, что последний вариант переменной отношения СЛУЖ_ПРО_ЗАДАН находится в BCNF, поскольку все атрибуты заголовка отношения входят в состав единственно возможного ключа. В этом отношении вообще отсутствуют нетривиальные FD. Поэтому ранее обсуждавшиеся принципы нормализации здесь неприменимы, но, тем не менее, мы получили полезную декомпозицию. Все дело в том, что в случае четвертого варианта отношения СЛУЖ_ПРО_ЗАДАН мы имеем дело с новым видом зависимости, впервые обнаруженным Роном Фейджином в 1971 г. Фейджин назвал зависимости этого вида многозначными (multi-valued dependency – MVD). Как мы увидим немного позже, MVD является обобщением понятия FD.

В отношении СЛУЖ_ПРО_ЗАДАН выполняются две MVD: СЛУ_НОМ

ПРО_НОМ и СЛУ_НОМ
СЛУ_ЗАДАН. Первая MVD означает, что каждому значению атрибута СЛУ_НОМ соответствует определяемое только этим значением множество значений атрибута ПРО_НОМ. Другими словами, в результате вычисления алгебраического выражения

(СЛУЖ_ПРО_НОМ WHERE (СЛУ_НОМ = сн AND СЛУ_ЗАДАН = сз)) PROJECT {ПРО_НОМ}

для фиксированного допустимого значения сн и любого допустимого значения сз мы всегда получим одно и то же множество значений атрибута ПРО_НОМ. Аналогично трактуется вторая MVD.

В переменной отношения R с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A (A

B) в том и только в том случае, когда множество значений атрибута B, соответствующее паре значений атрибутов A и C, зависит от значения A и не зависит от значения C.

Многозначные зависимости обладают интересным свойством «двойственности», которое демонстрирует следующая лемма.

Лемма Фейджина

В отношении R {A, B, C} выполняется MVD A

B в том и только в том случае, когда выполняется MVD A
C.

Доказательство достаточности условия леммы. Пусть выполняется MVD A

B. Пусть имеется некоторое удовлетворяющее этой зависимости значение r переменной отношения R, a обозначает значение атрибута A в некотором кортеже тела Br, а {b} – множество значений атрибута B, взятых из всех кортежей Br, в которых значением атрибута A является a.


Начало  Назад  Вперед