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

Третья нормальная форма

Вторая нормальная форма

Полная функциональная зависимость. Пусть А – это некоторый атрибут, Х – это набор атрибутов. Говорят, что А функционально полно зависит от Х, если Х ® А, Y А, где Y любое подмножество Х. Набор атрибутов Х называют детерминантом отношения. Отношение находится во второй нормальной форме, если оно находится в первой нормальной форме, и каждый неключевой атрибут функционально полно зависит от возможного ключа. Так, отношение с зависимостью Сном, Лном, Тном®Сном не находится во второй нормальной форме.

Транзитивная зависимость. Пусть X, Y, Z – наборы атрибутов некоторого отношения.

Если X®Y, Y®Z но Y Х то X®Z , тогда говорят что Z транзитивно зависит от X

Пример: транзитивной зависимости Сном®Тном, Тном®Лном Þ Сном®Лном.

Отношение находится в третьей нормальной форме, если оно находится во второй нормальной форме и каждый неключевой атрибут нетранзитивно зависит от ключа.

В общем случае отношение в третьей нормальной форме содержит аномалии, но если в отношении только один ключ и имеются зависимости только от ключа, оно будет свободно от аномалий.

Третья усиленная форма или нормальная форма Бойса–Кодда (НФБК)

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

Кодд доказал, что отношение в НФБК практически не содержит аномалий, поэтому на практике придерживаются приведения отношения в НФБК.

Декомпозиция получается приведением к получению двух отношений из одного.

Например, было R(X,Y,Z), а в результате декомпозиции получили два R₁(X,Y), R₂(Y,Z).

Декомпозиция аномального отношения выполняется следующим образом.

Пусть R – отношение, не находящееся в НФБК. Пусть a_j зависит от a_i (a_i ® a_j). Эта зависимость препятствует нахождению отношения в НФБК. Пусть a_i – некоторый атрибут, детерминант, но не являющийся возможным ключем . Отношение R(a₁,…,a_i,…,a_j) разбивают на два

R₁ (a₁,…,a_i,…,a_j-1) и R₂(a_i,a_j)

Отношение R₂ называется проекцией отношения R.

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

Теория реляционных баз данных говорит, что результаты запроса будут совпадать, если декомпозиция выполнена способом, при котором соединение R₁ и R₂ дает в точности исходное соотношение R – это декомпозиция без потерь.

Если естественное соединение R₁ и R₂ в итоге дает больше кортежей, чем в R – то это декомпозиция с потерями.

Отсутствие потерь при декомпозиции отношения R(X,Y,Z) в R₁(X,Y), R₂(Y,Z) гарантируется при условии, что от общего атрибута (Y) функционально зависит хотя бы один атрибут из двух оставшихся.

Пример 1:

Таблица 6.13 R (X,Y,Z).

X

Y

Y

X

Y

Z

Y Х Y Z

Декомпозиция

Таблица 6.14 R1 (X,Y).

Таблица 6.15 R2 (X,Z).

X

Y

Y

Z

Соединение

Таблица 6.16 R3 (X,Y,Z).

X

Y

Z

лишний кортеж

лишний кортеж

Так как Y

X, Y

Z, то R ≠ R3.

Пример 2:

Если Y → Z, то разбивая отношение R, получим, что R = R3.

Таблица 6.17 R (X,Y,Z).

X

Y

Z

Y

Z

Изменим строчку мешающую

зависимости Y → Z

Декомпозиция

Таблица 6.18 R1 (X,Y).

Таблица 6.19 R2 (Y,Z).

X

Y

Y

Z

Соединение

Таблица 6.20 R3 (X,Y,Z).

X

Y

Z