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

Смотрите здесь лАЗЕРНОЕ ФИЗИОТЕРАПЕВТИЧЕСКОЕ ОБОРУДОВАНИЕ. |

Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - часть 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} является декомпозицией без потерь.




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



Книжный магазин