ВВЕДЕНИЕ В СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ


4НФ (Четвертая Нормальная Форма) - часть 4


Однако Фейджином Р. [52] доказана следующая теорема:

Теорема (Фейджина). Пусть

,
,
- непересекающиеся множества атрибутов отношения
.

Декомпозиция отношения

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

Замечание. Если зависимость

является тривиальной, т.е. существует одна из функциональных зависимостей
или
, то получаем теорему Хеза.

Доказательство теоремы.

Необходимость. Пусть декомпозиция отношения

на проекции
и
является декомпозицией без потерь. Докажем что
.

Предположим, что отношение

содержит кортежи
и
. Необходимо доказать, что кортеж
также содержится в
. По определению проекций, кортеж
содержится в
, а кортеж
содержится в
. Тогда кортеж
содержится в естественном соединении
, а в силу того, что декомпозиция является декомпозицией без потерь, этот кортеж содержится и в
. Необходимость доказана.

Достаточность. Пусть имеется многозначная зависимость

. Докажем, что декомпозиция отношения
на проекции
и
является декомпозицией без потерь.

Как и в доказательстве теоремы Хеза, нужно доказать, что

для любого состояния отношения
.

Включение

доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения
.

Докажем включение

. Пусть кортеж
. Это означает, что в проекции
содержится кортеж
, а в проекции
содержится кортеж
. По определению проекции, найдется такое значение
атрибута
, что отношение
содержит кортеж
. Аналогично, найдется такое значение
атрибута
, что отношение
содержит кортеж
. Тогда по определению многозначной зависимости кортеж
. Включение доказано. Достаточность доказана. Теорема доказана.

Определение 4. Отношение

находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:




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