будет декомпозицией без потерь тогда
Однако Фейджином Р. [52] доказана следующая теорема:
Теорема (Фейджина). Пусть
,
,
- непересекающиеся множества атрибутов отношения
.
Декомпозиция отношения
на проекции
и
будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость
.
Замечание. Если зависимость
является тривиальной, т.е. существует одна из функциональных зависимостей
или
, то получаем теорему Хеза.
Доказательство теоремы.
Необходимость. Пусть декомпозиция отношения
на проекции
и
является декомпозицией без потерь. Докажем что
.
Предположим, что отношение
содержит кортежи
и
. Необходимо доказать, что кортеж
также содержится в
. По определению проекций, кортеж
содержится в
, а кортеж
содержится в
. Тогда кортеж
содержится в естественном соединении
, а в силу того, что декомпозиция является декомпозицией без потерь, этот кортеж содержится и в
.
Необходимость доказана.
Достаточность. Пусть имеется многозначная зависимость
. Докажем, что декомпозиция отношения
на проекции
и
является декомпозицией без потерь.
Как и в доказательстве теоремы Хеза, нужно доказать, что
для любого состояния отношения
.
Включение
доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения
.
Докажем включение
. Пусть кортеж
. Это означает, что в проекции
содержится кортеж
, а в проекции
содержится кортеж
. По определению проекции, найдется такое значение
атрибута
, что отношение
содержит кортеж
. Аналогично, найдется такое значение
атрибута
, что отношение
содержит кортеж
. Тогда по определению многозначной зависимости кортеж
. Включение доказано.
Достаточность доказана.
Теорема доказана.
Определение 4. Отношение
находится в
четвертой нормальной форме (
4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий
