Пример 2.17. MV-зависимость РЕЙС→→ДЕНЬ-НЕДЕЛИ выполняется для отношения Назначение в состоянии табл. 2.8, но не табл. 2.10. Состояние табл. 2.8 удовлетворяет также MVзависимости РЕЙС→→ТИП-САМОЛЕТА. Тот факт, что состояние отношения Назначение (табл.2.8) удовлетворяет двум MV-зависимостям, не является случайным [10].

2.4.3.10.Аксиомы вывода многозначных зависимостей

Вразд. 2.4.3.2 определены аксиомы вывода функциональных зависимостей.

Первые шесть аксиом вывода, приведенные ниже, являются аналогами одноименных аксиом для F- зависимостей, однако только первые три из них содержат похожие утверждения. Аксиома М7 не имеет аналога в F-зависимостях [10]. Пусть r – отношение со схемой R и W, X, Y, Z – подмножества R.

M1. Рефлексивность. Отношение r удовлетворяет Х→→Х.

М2. Пополнение. Если r удовлетворяет Х→→Y, то оно удовлетворяет XZ→→Y.

М3. Аддитивность. Если r удовлетворяет X→→Y и X→→Z, то оно Удовлетворяет X→→YZ.

М4. Проективность. Если r удовлетворяет X→→Y и X→→Z, то оно удовлетворяет X→→YÇZ и X→→Y-Z.

М5. Транзитивность. Если r удовлетворяет Х→→Y и Y→→Z, то r удовлетворяет X→→Z-Y.

М6. Псевдотранзитивность. Если r удовлетворяет X→→Y и YW→→Z, то r удовлетворяет XW→→Z- (YW).

М7. Дополнение. Если r удовлетворяет Х→→Y и Z = R – (XY), то г удовлетворяет X→→Z.

Система аксиом вывода M1–M7 для MV-зависимостей является полной [10].

Обратимся к следствиям, которые можно вывести из множества F- и MV-зависимостей. Для их комбинации существуют только две аксиомы.

Пусть r – отношение со схемой R; W, X, Y, Z – подмножества R.

С1. Копирование. Если r удовлетворяет X→Y, то r удовлетворяет X→→Y.

С2. Объединение. Если r удовлетворяет X→→Y и Z→W, где WÍY и YÇZ = Æ, то r удовлетворяет Х→W.

Системы аксиом F1–F6, M1–М7, С1 и С2 для множеств F- и MV-зависимостей являются полными [10

].

2.4.3.11. Четвертая нормальная форма

Известно, что каждое отношение r(R), удовлетворяющее MV-зависимости X→→Y, разлагается без потерь на отношения со схемами XY и XZ, где Z = R - (XY). Однако в случае если X→→Y – единственная зависимость в R, то R находится в ЗНФ. Таким образом, ЗНФ не определяет все возможные декомпозиции.

MV-зависимость Х→→Y называется тривиальной для произвольной схемы R, содержащей XY, если любое отношение r(R) удовлетворяет X→→Y [10].

MV-зависимость Х →→Y приложима к схеме R, если XYÍR.

Пусть F – множество F- и MV-зависимостей над U. Схема отношения RÍU находится в четвертой нормальной форме (4НФ) относительно F, если для каждой MV-зависимости X→→Y, выводимой из F и приложимой к R, либо MV-зависимость тривиальна, либо X является суперключом для Л [10].

Схема базы данных R находится в четвертой нормальной форме относительно F, если каждая входящая в нее схема отношения находится в четвертой нормальной форме относительно F.

Множество F из F-зависимостей и MV-зависимостей, аналогично тому как это делается для построения схем баз данных в ЗНФ, может быть использовано для построения декомпозиций схемы отношения R, находящихся в 4НФ. Для этого, начав с R, ищем выводимую из F нетривиальную MVзависимость Х→→Y, для которой X не является ключом R. Далее R разлагаем на два отношения R1=(Х, Y) и R2=(X, Z), где Z=R-(XY). MV-зависимость X→→Y теперь тривиальна в R1 и неприложима к R2. Процесс декомпозиции повторяем для той из схем R1 и R2, которая не находится в 4НФ относительно F. Поскольку используемые MV-зависимости не являются тривиальными, обе возникающие реляционные схемы содержат меньше атрибутов, чем исходные. Таким образом, процесс декомпозиции неизбежно

67

закончится.

2.4.3.12. Зависимости соединения

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

Пример 2.18. Отношение r со схемой ABC на рис. 2.26 разлагается без потерь на схемы АВ, АС и ВС (рис.2.27). Однако r не удовлетворяет никаким нетривиальным MV-зависимостям и, следовательно, не имеет декомпозиций без потери информации на пары R1, R2, такие, что R1 ≠ (A, В, С) и R2 ≠ (A, В, С).

Рис. 2.26. Пример отношения

Рис. 2.27. Пример декомпозиции

Пусть R={R1, ..., Rp} – множество реляционных схем над U. Отношение r(U) удовлетворяет зависимости соединения (J-зависимости) *[R1, R2, ..., Rp], если r разлагается без потерь на R1, R2, ..., Rp.

Пример 2.19. Отношение r на рис. 2.26 удовлетворяет J-зависимости *[АВ, АС, ВС].

Необходимым условием выполнения в отношении r(U) J-зависимости *[R1, R2, ..., Rp] является равенство U=R1R2...Rp. Из определения также видно, что MV-зависимость является частным случаем J- зависимости. Отношение r(R) удовлетворяет MV-зависимости X→→Y тогда и только тогда, когда r разлагается без потерь на XY и XZ, где Z=R-(XY). Условие совпадает с J-зависимостью *[XY, XZ]. С

другой стороны, зависимость соединения *[R1, R2] имеет тот же смысл, что MV-зависимость R1 Ç R2 →→

R1.

Для J-зависимости можно привести определение, аналогичное определению MV-зависимости [10]. Пусть r удовлетворяет зависимости *[R1, R2, ..., Rp]. Если r содержит кортежи t1, t2, ..., tp, такие, что для всех i, j

то r содержит кортеж t, такой, что t(Ri) = ti(Ri), 1 ≤ i ≤ p.

68

2.4.3.13. Пятая нормальная форма

Целью поиска декомпозиций без потери информации является устранение избыточности из отношений. В терминах поиска декомпозиций без потерь 4НФ не является наилучшим решением.

J-зависимость *[R1, R2,..., Rp] над R называется тривиальной, если она удовлетворяется в любом отношении r(R) [10].

J-зависимость соединения *[R1, R2, ..., Rp] приложима к реляционной схеме, если R=R1R2...Rp.

Пусть R – схема отношения и F – множество F- и J-зависимостей над R. Схема R находится в пятой нормальной форме (5НФ) относительно F, если для каждой J-зависимости *[R1, R2, ..., Rp], выводимой из F и приложимой к R, J-зависимость тривиальна или каждое Ri является сверхключом R [10].

Схема базы данных R находится в пятой нормальной форме относительно F, если в этой форме находится каждая схема R из R.

Приведем еще одно определение 5НФ [10].

Пусть R – схема отношения и F – множество F- и J-зависимостей. R находится в пятой нормальной форме (5НФ) относительно F, если для каждой J-зависимости *[R1, R2, ..., Rp], выводимой из F и приложимой к R, зависимость *[R1, R2, ..., Rp] выводима из ключевых F-зависимостей в R.

2.4.3.14. Обобщение этапов нормализации

Упрощенная обобщенная схема этапов нормализации отношений с привязкой к известным нормальным формам, выполняемая на этапе логического проектирования базы данных, представлена на рис. 2.28.

Рис. 2.28. Обобщенная схема процесса нормализации

69