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

Пусть R – реляционная схема; X и Υ – непересекающиеся множества на R и Z = R – (ΧΥ). Отношение 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(R) удовлетворяет MV-зависимости X→→Y и Z = R- (XY), то к удовлетворяет X →→ Z, (X Ç Υ) = Æ (пусто).

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

Теорема. Пусть r – отношение со схемой R; X, Y, Z Ì R такие, что Z = R – (XY). Отношение r(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) Î r.

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

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

Сс [AB = ab] (r) = 2, Co [AB = ab](r) = 2,

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

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

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

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

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

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

М4. Проективность: если Х →→ Υ и Χ →→ Ζ, то Χ →→ ΥÇΖ, 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 Ç W) = t3(Y ÇW) = t1(YÇW) = t(Y Ç W) и t4(YZ) = t(YZ). Поскольку U Í (R – XY) Ç (R – XZ) == V Ç W, то t4(X) = t4(U) = t3(U) = = t(U).

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

С1. Копирование: если имеется r(R) и X → Y, то X →→ Y.

С2. Объединение: если X→→Y и Z →→ W, где W Y и Y Ç 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(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 Í 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} не является навязанной.