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

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

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

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

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

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

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

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

В отношении R {A, B, C}выполняется MVDABв том и только в том случае, когда выполняется MVDAC.

Доказательство достаточности условия леммы.Пусть выполняется MVDAB. Пусть имеется некоторое удовлетворяющее этой зависимости значениеrпеременной отношенияR,aобозначает значение атрибутаAв некотором кортеже телаB_r,а {b}– множество значений атрибутаB, взятых из всех кортежейB_r, в которых значением атрибутаAявляетсяa. Предположим, что для этого значенияaMVDACне выполняется. Это означает, что существуют такое допустимое значениеcатрибутаCи такое значениеb{b}, что кортеж{a, b, c}B_r. Но это противоречит наличию MVDAB. Следовательно, если выполняется MVDAB, то выполняется и MVDAC. Аналогично можно доказать необходимость условия леммы.

Таким образом, MVD ABиACвсегда составляют пару. Поэтому обычно их представляют вместе в формеA B | C.

FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FDAB, то выполняется и MVDAB.³⁹⁾

Мы видим, что отношения СЛУЖ_ПРО_НОМиСЛУЖ_ЗАДАНИЕне содержат MVD, отличных от FD, и именно в этом выигрывает декомпозиция изрис. 9.2. Правомочность этой декомпозиции доказывается приведенной ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хита.

Теорема Фейджина

Пусть имеется переменная отношения Rс атрибутамиA,B,C(в общем случае, составными). ОтношениеRдекомпозируется без потерь на проекции{A, B}и{A, C}тогда и только тогда, когда для него выполняется MVDA B | C.

Докажем достаточность условия теоремы.Пустьrявляется некоторым допустимым значением переменной отношенийR. Пустьaесть значение атрибутаAв некотором кортеже телаB_r,{b}– множество значений атрибутаB, взятых из всех кортежей телаB_r, в которых значением атрибутаAявляетсяa, и{c}– множество значений атрибутаC, взятых из всех кортежей телаB_r, в которых значением атрибутаAявляетсяa. Тогда очевидно, что в тело значенияr PROJECT {A, B}будут входить все кортежи вида{a, b_i}, гдеb_i{b}, и если некоторый кортеж{a, b_j}входит в тело значения отношенияr PROJECT {A, B}, тоb_j{b}. Аналогичные рассуждения применимы кr PROJECT {A, C}. Очевидно, что из этого следует, что при наличии многозначной зависимостиA B | Cв переменной отношенияR{A, B, C}декомпозицияrна проекцииr PROJECT {A, B}иr PROJECT {A, C}является декомпозицией без потерь.

Для доказательства необходимости условия теоремы предположим, что декомпозиция переменной отношения R {A, B, C}на проекцииR PROJECT {A, B}иR PROJECT {A, C}является декомпозицией без потерь для любого допустимого значенияrпеременной отношенияR. Мы должны показать, что в телеB_rзначения-отношенияrподдерживается ограничение

IF ({a, b₁, c₁}; B_r AND {a, b₂, c₂} B_r)

THEN ({a, b₁, c₂} B_r AND {a, b₂, c₁} B_r)

Действительно, пусть в B_rвходят кортежи{a, b₁, c₁}и{a, b₂, c₂}. Предположим, что{a, b₁, c₂} B_r OR a, b₂, c₁ B_r. Но в тело значения отношенияr PROJECT {A, B}входят кортежи{a, b₁}и{a, b₂}, а в тело значения переменной отношенияr PROJECT {A, C}–{a, c₁}и{a, c₂};. Очевидно, что в тело значения естественного соединенияr PROJECT {A, B} NATURAL JOIN r PROJECT {A, C}войдут кортежи{a, b₁, c₂}и{a, b₂, c₁}, и наше предположение об отсутствии по крайней мере одного из этих кортежей вB_rпротиворечит исходному предположению о том, что декомпозицияrна проекцииr PROJECT {A, B}иr PROJECT {A, C}является декомпозицией без потерь. Тем самым, теорема Фейджина полностью доказана.Конец доказательства.

39 Упражнение по ходу лекции. Пусть имеется отношение r с атрибутами A , B , C (в общем случае, составными), в котором существует FD AB . Что в этом случае можно сказать про зависимость атрибутов A и C ?

Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей «аномальные» многозначные зависимости, с приведением отношений в четвертую нормальную форму.

Переменная отношения rнаходится вчетвертой нормальной форме (4NF)в том и только в том случае, когда она находится в BCNF, и все MVDrявляются FD с детерминантами – возможными ключами отношенияr.

В сущности, 4NF является BCNF, в которой многозначные зависимости вырождаются в функциональные (позволим себе на один момент отказаться от сокращений). Понятно, что отношение СЛУЖ_ПРО_ЗАДАНне находится в 4NF, поскольку детерминант MVDСЛУ_НОМПРО_НОМиСЛУ_НОМСЛУ_ЗАДАНне является возможным ключом, и эти MVD не являются функциональными. С другой стороны, отношенияСЛУЖ_ПРО_НОМиСЛУЖ_ЗАДАНИЕнаходятся в BCNF и не содержат MVD, отличных от FD с детерминантом – возможным ключом. Поэтому они находятся в 4NF.