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

Предположим, что для этого значения a MVD A

C не выполняется. Это означает, что существуют такое допустимое значение c атрибута C и такое значение b

{b}, что кортеж {a, b, c}

Br. Но это противоречит наличию MVD A

B. Следовательно, если выполняется MVD A

B, то выполняется и MVD A

C. Аналогично можно доказать необходимость условия леммы.

Таким образом, MVD A

B и A

C всегда составляют пару. Поэтому обычно их представляют вместе в форме A

B | C.

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

B, то выполняется и MVD A

B .

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

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

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

B | C.

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

{b}, и если некоторый кортеж {a, bj} входит в тело значения отношения r PROJECT {A, B}, то bj

{b}. Аналогичные рассуждения применимы к r PROJECT {A, C}. Очевидно, что из этого следует, что при наличии многозначной зависимости A

B | C в переменной отношения R{A, B, C} декомпозиция r на проекции r PROJECT {A, B} и r PROJECT {A, C} является декомпозицией без потерь.

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