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

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

Доказательство достаточности условия леммы. Пусть выполняется MVD A B. Пусть имеется некоторое удовлетворяющее этой зависимости значение V_r переменной отношения r, a обозначает значение атрибута A в некотором кортеже тела V_r, а {b} – множество значений атрибута B, взятых из всех кортежей тела V_r, в которых значением атрибута A является a. Предположим, что для этого значения a MVD A C не выполняется. Это означает, что существуют такое допустимое значение c атрибута C и такое значение b {b}, что кортеж <a, b, c> V_r. Но это противоречит наличию 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, и именно в этом выигрывает декомпозиция из рис. 8.2. Правомочность этой декомпозиции доказывается приведенной ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хита.

Дата добавления: 2015-04-29