Пример 3.46. Рассмотрим отношение на рис. 3.39 с многозначной зависимостью

пате street city

Согласно правилу дополнительности, для этого отношения должна быть истинной и зависимость

name title year

так как атрибуты title и year не упоминакяся в первой зависимости. С интуитивной точки зрения вторая зависимость означает, что каждая кинозвезда снималась во множестве фильмов, которое не зависит от ее адресов. □

3-8.4 Четвертая нормальная форма

Избыточность, показанную в разделе 3.8.! и вызванную многозначными зависимостями, можно устранить, если применить эти зависимости в новом алгоритме декомпозиции отношений. В Этом разделе вводится еще одна нормальная форма - четвергал нормальная фор.ма. в которой устраняются все нетривиальные (смысл этого определения раскрывается ниже) многозначные зависимости, как удалялись все функциональные зависимости, нарушающие BCNF. В результате разложенные отношения (см. раздел 3.7.1) освобождаются от избыточности, вызванной и функциональными, II многозначными зависимостями (см. раздел 3.8.1).

Многозначная зависимость Aj Aj... А - В, Bi... В , для отношения R нетрипи-альна, если:

1. Ни один афибут В,- не входит в атрибуты А\, .... А .

2. А,. А и В В не исчерпывают всего множесгва атриб\тов отношения R.

Однако для многозначных зависимостей действует множество новых правил.

Каждая функциональная зависимость является многозначной зависимостью: если /), Ai... Л -* В Bj... В, , то Ах Aj... А В Л ... £ .

Покажем, почему это верно. Пусть Л -отношение, для которого истинна функциональная зависимость .4, /Ij .../! - В, Вг... В , а / и w - кортежи R, совпадающие по атрибутам /4,.....А . Чтобы доказать, что истинна многозначная зависимость

А, Aj...A - В, в2...В

нужно показать, что Л содержит кортеж v, совпадающий с / и и по атрибутам Af,.... А , с г по атрибутам В В, и с ы по всем остальным атрибутам. Кортеж v вполне может быть кортежем и. Несомненно, что и совпадает с / и и по атрибутам

А....., А . Согласно функиионапьной зависимости /}, Aj Д,- В, Bj... В кортеж и

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

0[едующее правило дополнительности не имеет аналога в мире функциональных зависимостей.

Если /1 /!i... Д,- В, В,... В , ,миогозначная зависимость для отношения Л, то Я удовлетворяет зависимости /), 4,... /} -w С, С,... Q, где все С, являются атрибутами В, которые не встречаются ни среди /},..... А , ни среди В В .

Условие четвертоП нормальной формы , по существу, является условием BCNF, относящимся не к функциональным, а к многозначным зависимостям. Формально:

OiHomeHiie Л находится в четвертой нормаший ipofwe (4NF), если всегда, когда многозначная зависимость

.4,.4,...Л-** В, В,... В

нетривиальна, {А,. Л, .... А ) - иадшноч.

Другими словами, если отношение наход1ггся в 4NF, любая нетривиальная многозначная зависимость - это функшюнальная зависимость с надключом п левой части. Заметим, что понятия юхючей и надключей связаны только функшюнальны-ми зависимостями; многозначные зависимости не изменяют определение ключа.

Пример 3.47. Отношение на рис. 3 39 нарушает условие 4NF. Например, многозначная зависимость

name ->-> street city

нетривиальна, но name не является надключом. Фактически единственный ключ для этого отношения - все его атрибуты. О

Четвертая нормальная форма -это обобщение BCNF. Любая функциональная зависимость является многозначной зависимостью. Значит, каждое нарушение BCNF - это нарушение 4NF. Другими словами, всякое отношение в 4NF находится в BCNF.

Однако есть отношения, которые находятся в BCNF, но не в 4NF. Хороший пример такого отношения приведен на рис. 3.39. Единственным ключом этого отношения являются все агрибуты, и здесь нет нетривиальных функциональных зависимостей. Таким образом, очевидно, что это BCNF, но ие 4NF, о чем свидетельствует пример 3.47.

3-8.5 Декомпозиция

в четвертую нормальную форму

Алгоритм декомпозишщ 4NF примерно такой же, как алгоритм декомпозиции BCNF. Мы находим нарушение 4NF, например А, А... А - By В... В ,

где {А А2.....А ] не является надключом. Заметим, что эта многозначная зависи-

моспь может быть истинной многозначной зависимостью, а может быть выведена из соолветсгвующеП функциональной зависимости /}, А-,... А В ... В, , так как любая функциональная зависимость является многозначной. Затем схему отношения Л, имеющую нарушение 4NF, разбиваем на две схемы:

1. Атрибуты At, А и атрибуты By..... В ,.

2. Атрибуты А......А и все атрибуты R, не совпадающие ни с At, ... А.

нн с В Б, .

Пример 3.48. Продолжим пример 3.47. Установлено, что

name-w street city

нарушает 4Nr. По правилу декомпозиции схему с пятью атрнбутагш нужно заменить схемой с тремя атрибутами из указанной многозначной зависимости и схемой, состоящей из ее левой часги name и aTpn6vroB, не входящих в данную зависимость. Такими атрибугами яачяются title и year. В рсзультаэе декомпозиции получаем схемы

Построение проеклсий многозначных отношений

проводя деко.чпозицию в четвертую нормальную форму, нужно найти многозначные зависимости, которые истинны для результата декомпозиции. Такой поиск желательно упростить. Однако простого теста, аналогичного вычислению замыкания множества атрибутов (см. раздел 3 6.3), не существует. Даже полное множество правил логических рассуждений о множествах функ-циональнЬ[х и многозначных зависимостей является очень сложным и выхо-t дит за рамки этой книги В списке литературы в конце главы указаны \ некоторые источники, где обсуждается эта тема.

I К счастью, релевантные многозначные зависимости для одного из про- дуктов декомпозиции часто можно найти с помощью правил транзитивности, S дополнительности и пересечения (упражнение 3.8.7(b)). Рекомендуем читателю j поработать с ними, анализируя примеры и выполняя упражнения.

Каждый шаг декомпозиции BCNF приводит к схемам, имеющим строго меньше атрибутов, чем исходные, поэтому в конечном счете получаются схемы, которые не нужно разлагать дальше, т.е. они находятся в 4NF, Более того, обоснование декомпозиции, приведенное в разделе 3.7.6, подходит и для многозначных зависимостей. Если декомпозиция отношения проводится согласно многозначной зависимости

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

3.8.6 Связи между нормальными формами

Как уже было сказано, 4NF влечет BCNF, а та, в свою очередь, 3Nr. Значит, для любой схемы отношений множества ее экземпляров, удовлетворяющие этим трем отношениям, связаны так, как показано на рис. 3.41. Если множество кортежей удовлетворяет условию 4NF, оно обязательно удовлетворяет и двум другим условиям нормальной формы, а если оно удовлетворяет BCNF, то обязательно находится в 3NF. Однако при определенных функциональных зависимостях, установ ленных для схемы, множества кортежей могут находиться в 3NF, но не в BCNF.

{name, street city} {name title, year}

Ни в одной из них нет нет1зивна/1ьных многозначных (или функциональных) зависимостей, поэтому они находятся в 4NF. Заметим, что в отношении со схемой {пате, street, city} многозначная зависимость

пате- street city

тривиальна, так как она содержит все атрибуты. Аналогично в отношении со схемой {name, ttle, year} многозначная зависимость

name-** title year

тривиальна. Еспи бы одна из схем или обе не были в 4NF, их пришлось бы разлагать дальше. □