Для доказательства необходимости условия теоремы

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

IF ({a, b1, c1};

Br AND {a, b2, c2}

Br) THEN ({a, b1, c2}

Br AND {a, b2, c1}

Br)

Действительно, пусть в Br входят кортежи {a, b1, c1} и {a, b2, c2}. Предположим, что {a, b1, c2}

Br OR a, b2, c1

Br. Но в тело значения отношения r PROJECT {A, B} входят кортежи {a, b1} и {a, b2}, а в тело значения переменной отношения r PROJECT {A, C} – {a, c1} и {a, c2};. Очевидно, что в тело значения естественного соединения r PROJECT {A, B} NATURAL JOIN r PROJECT {A, C} войдут кортежи {a, b1, c2} и {a, b2, c1}, и наше предположение об отсутствии по крайней мере одного из этих кортежей в Br противоречит исходному предположению о том, что декомпозиция r на проекции r PROJECT {A, B} и r PROJECT {A, C} является декомпозицией без потерь. Тем самым, теорема Фейджина полностью доказана. Конец доказательства.

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

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

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

ПРО_НОМ и СЛУ_НОМ

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

Упражнение по ходу лекции. Пусть имеется отношение r

с атрибутами A

, B

, C

(в общем случае, составными), в котором существует FD A

B

. Что в этом случае можно сказать про зависимость атрибутов A

и C

?

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий