Поделиться Поделиться

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

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

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

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

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

В переменной отношения r с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A (A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B) в том и только в том случае, когда множество значений атрибута B, соответствующее паре значений атрибутов A и C, зависит от значения A и не зависит от значения C.

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

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

В отношении r {A, B, C} выполняется MVD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B в том и только в том случае, когда выполняется MVD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 C.

Таким образом, MVD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B и A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 C всегда составляют пару. Поэтому обычно их представляют вместе в форме A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B | C.

FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B, то выполняется и MVD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B .

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

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

Пусть имеется переменная отношения r с атрибутами A, B, C (в общем случае, составными). Отношение r декомпозируется без потерь на проекции {A, B} и {A, C} тогда и только тогда, когда для него выполняется MVD A Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма - Инвестирование - 1 B | C.

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

Определение: Четвертая нормальная форма

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

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

2.3.10. Зависимости проекции/соединения и пятая нормальная форма

Приведение отношения к 4NF предполагает его декомпозицию без потерь на две проекции (как и в случае 2NF, 3NF и BCNF). Однако бывают (хотя и нечасто) случаи, когда декомпозиция без потерь на две проекции невозможна, но можно произвести декомпозицию без потерь на большее число проекций. Будем называть n-декомпозируемым отношением отношение, которое может быть декомпозировано без потерь на n проекций. До сих пор мы имели дело с 2-декомпозируемыми отношениями.

← Предыдущая страница | Следующая страница →