Алгоритм1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в нфбк.

Входные данные: схема отношения и функциональные зависимости .

Выходные данные: декомпозиция , обладающая свойством соединения без потерь, такая, что каждая схема отношения в декомпозиции находится в НФБК относительно проекции на эту схему.

Метод: декомпозиция для конструируется итеративным методом

. Существует ключ . Если схема отношения из и не находится в НФБК, то пусть – зависимость, имеющая место в , где не содержит ключа , а .

Тогда в должен существовать некоторый атрибут, который не принадлежит и не принадлежит . В противном случае содержал бы ключ . Заменим на и , где состоит из и атрибутов , а – из всех атрибутов , за исключением . и . (это удаление транзитивной зависимости .

Декомпозиция на и обладает свойством соединения без потерь относительно множества функциональных зависимостей, спроецированных на . Если в и существуют транзитивные зависимости, то делаем декомпозиции и для . Т.к. в и меньше атрибутов, чем в , мы достигнем в конце концов некоторого момента, когда любая схема отношения в будет находиться в НФБК. При этом обладает свойством соединения без потерь, т.к. начальное состояние состоит только из , и все модификации сохраняли свойство соединения без потерь.

 

 

Алгоритм 2: приведения отношения к 3НФ, использующей декомпозицию, сохраняющую функциональные зависимости.

Входные данные: схема отношения и множество функциональных зависимостей .

Выходные данные: сохраняющая зависимости декомпозиция схемы отношения такая, что каждая входящая в нее схема отношения находится в 3НФ относительно проекции на эту схему.

Метод: если существует некоторый атрибут в , участвующий в левой или правой части какой-либо зависимости из , то этот атрибут может сам по себе образовать некоторую схему отношения и его можно исключить из . Если в одной из зависимостей участвуют все атрибуты , то выходные данные образуют само . В противном случае декомпозиция, образующая выходные данные, состоит из схемы для каждой зависимости в . Если, однако, в имеются зависимости , то может быть использована схема вместо , и такая подстановка является предпочтительной.

Теорема: Пусть декомпозиция , образованная схемами отношений в 3НФ и построенная по алгоритму 2. Пусть ключ . Тогда декомпозиция такая, что все ее схемы отношений находятся в 3НФ. Эта декомпозиция сохраняет зависимости и обладает свойством соединения без потерь.

Пример:

В декомпозицию будут входить

 

МНОГОЗНАЧНЫЕ ЗАВИСИМОСТИ.

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

Пусть задана схема отношений , атрибуты . Существует (X мультиопределяет Y) – многозначная зависимость, если:

Из симметрии определения и следует, что в существует :

.

X Y Z

t₁

t₂

t₃