Файл: Систем управления.pdf

минимально. Атрибут D транзитивно зависит от А только через С.
Четвертая проблема состоит в том, что для построенной схемы базы данных заданное множество F- зависимостей может оказаться ненавязанным [10].
Пример 2.15. Пусть заданы схема R(A, В, С, D, Е) и F={A→BCDE, CD→E, CE→B}. Исключив транзитивную зависимость Е от А через CD, получаем
Множество F ненавязано схеме базы данных R={R
1
, R
2
} из-за того, что зависимость ЕС→В
невыводима из F-зависимостей в F
+
, приложимых к R
1
или R
2
(это утверждение должно быть подтверждено вычислением F
+
).
Наконец, пятая проблема. С помощью декомпозиции можно породить схемы со «скрытыми» трянзитивными зависимостями.
Пример 2.16. Пусть заданы схема R(A, В, С, D) и F={A→B, В→С}. Атрибуты AD являются ключом F, а В частично зависит от AD. При декомпозиции получаем
Несмотря на то что R
1
, R
2
формально находятся в ЗНФ, в R
1
существует «скрытая» транзитивная зависимость С от AD.
Чтобы избежать проблем, возникающих при декомпозиции схем отношений, необходимо использовать другие методы получения третьей нормальной формы, например, метод синтеза ЗНФ [10].
2.4.3.8. Нормальная форма Бойса–Кодда (НФБК)
Схема отношения R находится в нормальной форме Бойса-Кодда (НФБК) относительно множества F- зависимостей F, если она находится в 1НФ и никакой атрибут в R не зависит транзитивно ни от одного ключа R [10].
Схема базы данных R находится в нормальной форме Бойса-Кодда (НФБК) относительно множества
F-зависимостей F, если каждая схема отношения R
⊆
R находится в НФБК относительно F.
НФБК включает в себя ЗНФ [10].
Схема отношения R находится в нормальной форме Бойса-Кодда (НФБК) относительно множества F- зависимостей F, если для каждого подмножества Y из R и каждого атрибута A
∈
R-Y из Y→А следует
Y→R при F, т.е. если Y нетривиально определяет произвольный атрибут из R, то Y есть сверхключ R.
Для схемы отношения, не находящейся в НФБК, можно всегда провести декомпозицию в схему базы данных в НФБК [10].
С одной стороны, НФБК в некотором смысле является более сильной, чем ЗНФ, а значит, более желательной. Но, с другой стороны, НФБК имеет свои проблемы [10]. Из предыдущего изложения следует, что при заданном множестве F-зависимостей над R можно найти схему базы данных в ЗНФ, полностью характеризующую F. Для НФБК это неверно. Множество F-зависимостей может не иметь полной НФБК схемы базы данных, кроме того, проверка свойства НФБК для заданной схемы базы данных является NP-полной задачей.
2.4.3.9. Многозначные зависимости
Выше было показано, что присутствие функциональных зависимостей в реляционной схеме означает возможность декомпозиции схемы, уменьшающей избыточность и при этом сохраняющей информацию. Однако существование F-зависимостей не является необходимым условием такой
65

декомпозиции. Рассмотрим состояние отношения Назначение табл. 2.8.
Таблица 2.8
Назначение
РЕЙС
ДЕНЬ-НЕДЕЛИ
ТИП-САМОЛЕТА
106 106 106 106 204 204
Понедельник
Четверг
Понедельник
Четверг
Среда
Среда
747 747 1011 1011 707 727
Кортеж в отношении Назначение означает, что рейс № f может выполняться в день недели d на самолете типа р. В отношении не выполняются ни F-зависимость РЕЙС→ДЕНЬ-НЕДЕЛИ, ни
РЕЙС→ТИП-САМОЛЕТА, однако оно без потери информации разлагается на два отношения: РЕЙС
ДЕНЬ-НЕДЕЛИ и РЕЙС ТИП-САМОЛЕТА (табл. 2.9).
Таблица 2.9
День назначения
РЕЙС
ДЕНЬ-НЕДЕЛИ
106 106 204
Понедельник
Четверг
Среда
Тип самолета назначения
РЕЙС
ТИП-САМОЛЕТА
106 106 204 204 747 1011 707 727
Рассмотрим другое состояние отношения Назначение, задаваемое табл. 2.10. Если разложить это состояние на схемы (РЕЙС, ДЕНЬ-НЕДЕЛИ) и (РЕЙС, ТИП-САМОЛЕТА), то снова получится вариант из табл.2.9. Однако соединение отношений табл. 2.9 не восстанавливает исходного отношения.
Таблица 2.10
Назначение
РЕЙС
ДЕНЬ-НЕДЕЛИ
ТИП-САМОЛЕТА
106 106 106 204 204
Понедельник
Четверг
Четверг
Среда
Среда
747 747 1011 707 727
Каковы же свойства первого состояния отношения Назначение, отсутствующие у второго, которые обеспечивают декомпозицию без потери информации? В первом случае, если самолет некоторого типа использован для выполнения маршрута в один день, он может быть использован для выполнения этого маршрута в любой другой день. Это свойство отсутствует во втором состоянии отношения Назначение,
поскольку рейс №106 может использовать тип 1011 в четверг, но не в понедельник. Отношение в первом состоянии следует подвергнуть декомпозиции, ибо при заданном рейсе ДЕНЬ-НЕДЕЛИ не содержит информации об атрибуте ТИП-САМОЛЕТА, и наоборот.
Сформулируем это свойство по-другому. Если в отношении Назначение существуют кортежи
и , то должен быть кортеж . Формальное определение следующее [10].
Пусть R – реляционная схема, X и Y – непересекающиеся подмножества R, и пусть Z=R–(XY).
Отношение r(R) удовлетворяет многозначной зависимости (MV-зависимости) Х→→Y, если для любых двух кортежей t
1
и t
2
из r, для которых t
1
(X) = t
2
(X), в r существует кортеж t
3
для которого выполняются соотношения t
3
(X) = t
1
(X), t
3
(Y) = t
1
(Y),t
3
(Z) = t
2
(Z).
Из симметрии определения относительно t
1
и t
2
следует, что в г существует также в r для которого
t
4
(X) = t
1
(X), t
4
(Y) = t
2
(Y), t
4
(Z) = t
2
(Z).
66

Пример 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 разлагаем на два отношения R
1
=(Х,
Y) и R
2
=(X, Z), где Z=R-(XY). MV-зависимость X→→Y теперь тривиальна в R
1
и неприложима к R
2
.
Процесс декомпозиции повторяем для той из схем R
1
и R
2
, которая не находится в 4НФ относительно F.
Поскольку используемые MV-зависимости не являются тривиальными, обе возникающие реляционные схемы содержат меньше атрибутов, чем исходные. Таким образом, процесс декомпозиции неизбежно
67

закончится.
2.4.3.12. Зависимости соединения
Многозначные зависимости представляют собой попытку выделения декомпозиций без потери информации, сохраняющих это свойство для всех отношений с заданной схемой. Однако MV- зависимости не полностью в этом смысле адекватны. Отношение может иметь нетривиальную декомпозицию без потерь на три схемы, но не обладать таким свойством для любых двух из них.
Пример 2.18. Отношение r со схемой ABC на рис. 2.26 разлагается без потерь на схемы АВ, АС
и ВС (рис.2.27). Однако r не удовлетворяет никаким нетривиальным MV-зависимостям и, следовательно, не имеет декомпозиций без потери информации на пары R
1
, R
2
, такие, что R
1
≠ (A,
В, С) и R
2
≠ (A, В, С).
Рис. 2.26. Пример отношения
Рис. 2.27. Пример декомпозиции
Пусть R={R
1
, ..., R
p
} – множество реляционных схем над U. Отношение r(U) удовлетворяет
зависимости соединения (J-зависимости) *[R
1
, R
2
, ..., R
p
], если r разлагается без потерь на R
1
, R
2
, ..., R
p
.
Пример 2.19. Отношение r на рис. 2.26 удовлетворяет J-зависимости *[АВ, АС, ВС].
Необходимым условием выполнения в отношении r(U) J-зависимости *[R
1
, R
2
, ..., R
p
] является равенство U=R
1
R
2
...R
p
. Из определения также видно, что MV-зависимость является частным случаем J- зависимости. Отношение r(R) удовлетворяет MV-зависимости X→→Y тогда и только тогда, когда r
разлагается без потерь на XY и XZ, где Z=R-(XY). Условие совпадает с J-зависимостью *[XY, XZ].С другой стороны, зависимость соединения *[R
1
, R
2
] имеет тот же смысл, что MV-зависимость R
1
∩
R
2 →→
R
1
.
Для J-зависимости можно привести определение, аналогичное определению MV-зависимости [10].
Пусть r удовлетворяет зависимости *[R
1
, R
2
, ..., R
p
].Если r содержит кортежи t
1
, t
2
, ..., t
p
, такие, что для всех i, j
то r содержит кортеж t, такой, что t(R
i
) = t
i
(R
i
), 1 ≤ i ≤ p.
68

2.4.3.13. Пятая нормальная форма
Целью поиска декомпозиций без потери информации является устранение избыточности из отношений. В терминах поиска декомпозиций без потерь 4НФ не является наилучшим решением.
J-зависимость *[R
1
, R
2
,..., R
p
]над R называется тривиальной, если она удовлетворяется в любом отношении r(R) [10].
J-зависимость соединения *[R
1
, R
2
, ..., R
p
] приложима к реляционной схеме, если R=R
1
R
2
...R
p
.
Пусть R – схема отношения и F – множество F- и J-зависимостей над R. Схема R находится в пятой
нормальной форме (5НФ) относительно F, если для каждой J-зависимости *[R
1
, R
2
, ..., R
p
],выводимой из
F и приложимой к R, J-зависимость тривиальна или каждое R
i
является сверхключом R [10].
Схема базы данных R находится в пятой нормальной форме относительно F, если в этой форме находится каждая схема R из R.
Приведем еще одно определение 5НФ [10].
Пусть R – схема отношения и F – множество F- и J-зависимостей. R находится в пятой нормальной
форме (5НФ) относительно F, если для каждой J-зависимости *[R
1
, R
2
, ..., R
p
],выводимой из F и приложимой к R, зависимость *[R
1
, R
2
, ..., R
p
] выводима из ключевых F-зависимостей в R.
2.4.3.14. Обобщение этапов нормализации
Упрощенная обобщенная схема этапов нормализации отношений с привязкой к известным нормальным формам, выполняемая на этапе логического проектирования базы данных, представлена на рис. 2.28.
Рис. 2.28. Обобщенная схема процесса нормализации
69