Функциональные многозначные MV-зависимости

Пусть R — реляционная схема; X и? — непересекающиеся множества на R и Z = R — (??). Отношение r® удовлетворяет многозначной MV-зависимости X >> Y, если для любых кортежей t1 и t2 из r, для которых t1(X) = t2(Х) в r существует кортеж t3 такой, что t3(X) = t1(X), t3(Y) = t1(Y), t3(Z) = t2(Z) (рис. 4.2.).

Из симметрии существует и кортеж t4 такой, что t4(X) = t1(X), t4(Y) = t2(Y) t4(Z) = t1(Z).

Рис. 4.2. MV-зависимость.

Лемма. Если отношение r® удовлетворяет MV-зависимости X>>Y и Z = R- (XY), то к удовлетворяет X >> Z, (X C ?) =? (пусто).

Иначе говоря, если существуют кортежи fdp и fd’p', то должны быть и fd’p, и fdp'.

Теорема. Пусть r — отношение со схемой R; X, Y, Z I R такие, что Z = R — (XY). Отношение r® удовлетворяет MV-зависимости X >> Y тогда и только тогда, когда r без потери информации раскладывается в отношения со схемами R1 = XY и R3 = XZ.

АВ >> ВС и АВ >> С имеет вид.

Проверка выполнения X >>Y возможна двумя способами.

• 1. {XY} NJ {X (R — XY)} = Z, где NJ — операция слияния.
• 2. Пусть Z = R — (XY), R1 = XY, R2= XZ. Если , то (r1)NJ (r2) I r.

Пусть для х I X существует с1 кортежей в r1 и с2 в r2 со значением х. Пусть с — число кортежей в r. Если для любого х I X = с1 + с2, то r = (r1)NJ (r2).

Пример 4.2. Введем обозначения:

Сс [AB = ab] ® = 2, Co [AB = ab]® = 2,.

CABCD = CcCd и R1 = ABC; Z = R — ABC = D; R2 = ABD.

Пусть R — схема отношений и X, Y, Z, W I R.

Для MV-зависимостей существует ряд аксиом, которые по своему виду несколько отличны от аксиом F-зависимостей.

Ml. Рефлексивность: X >> X.

М2. Пополнение: если X >> Y, то XZ >> Y.

М3. Аддитивность: если Х >>? и? >> ?, то X YZ. Эти аксиомы похожи на аксиомы F-зависимостей.

М4. Проективность: если Х >>? и? >> ?, то? >> ?C?, X >> Y — Z.

M5. Транзитивность: если X >> Y и Y >> Z, то X >> Z — Y.

М6. Псевдотранзитивность: если X > Y и YW > Z, то XW >> Z — YW.

Следующая аксиома не имеет аналога для F-зависимостей.

М7. Дополнение: если X >> Y и Z = R — (XY), то X >> Z.

Докажем только аксиому М3, поскольку остальные доказательства похожи по своей идее.

Из X «Y следует существование кортежа t1 со свойствами t3(X) = t1(X), t3(Y) == t2(Y), t3(V) = t2(V), где V = R — (XY).

Аналогично из X >> Z следует t4(X) = t1(X), t4(Z) = t1(Z), t4(W) = t2(W), где W = R — (XZ).

Надо найти кортеж t (X) = t1(X), t (YZ) = t1(YZ), t (U) = t2(U), где U = R — (XYZ). Пусть t = t4. Тогда t (X) = t4(X), t4(Z) = t (Z), t4(Y) = t4(Y C W) = t3(Y CW) = t1(YCW) = t (Y C W) и t4(YZ) = t (YZ). Поскольку U I (R — XY) C (R — XZ) == V C W, то t4(X) = t4(U) = t3(U) = = t (U).

Когда речь идет об MV-зависимостях, то вместе с ними могут существовать и F-зависимости. Fи MV-зависимости связаны двумя аксиомами.

С1. Копирование: если имеется r® и X > Y, то X >> Y.

С2. Объединение: если X>>Y и Z >> W, где W Y и Y C Z = , то X>> W.

Можно показать, что:

• 1) система Ml-М7 полна;
• 2) система FI-F6, Ml-М7, Cl-С2 для множеств Fи MV-зависимостей полна.

Свойства Fи MV-зависимостей используем в § 4.2 в процедуре нормализации.

В ней участвуют две составляющие:

• 1) F-зависимости, которые дают возможность получить 1НФ, 2НФ, 3НФ, а также нормальную форму Бойса-Кодда (НФБК);
• 2) MV-зависимости, связанные с 4НФ и 5НФ.

F-зависимости. Основное правило: необходимо, чтобы r® разлагалось на отношения (схемы), например, R1 и R2, без потерь, т. е.

Нормализация возможна через декомпозицию или методом синтеза.

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

Говорят, что F-зависимость X > Y применима к схеме R, если X > Y является F-зависимостью над R. Пусть БД d = {r1, …, rn} со схемой R = {R1, …, Rn] и F-множество F-зависимостей над U. БД d удовлетворяет F, если любая F зависимость X > Y из F+ применима к схеме R и выполняется отношение r.

В общем случае F может быть избыточно и потому выявляют G I F и G = F. Говорят, что G навязан схеме R и используют G-зависимость для композиции.

Пусть G-множество всех F-зависимостей в F+, которые применимы к какой-либо схеме Rie R. Любая F-зависимость в G+ называется навязанной R, любая F-зависимость (F±G+) — ненавязанной R. Множество F навязано схеме R БД, если любая G-зависимость в F+ навязана R, т. e. G e F.

Пример 4.3. Пусть R = {R1, R2, R3}, R1 = ABC, R2= BCD, R3= DE и F = {А? > ВС, С > А, А> D, D > Е, А > Е}. А > D и, А > Е неприменимы ни к одной схеме R. Однако F навязано R, как G = {А > ВС, С > А, С > D, D > E} º F и каждая F-зависимость в G применима к некоторой схеме в R. F' = {А > D} не является навязанной.