Понятие многозначной зависимости

Отношение может находиться в 3НФ или в НФБК и обладать нежелательными свойствами. Рассмотрим от­ношение СБЫТ (табл. 3.7).

Кортеж <z t m> означает, что завод z производит товар t и снабжает магазин m. Предположим, что завод произ­водит различные товары и снабжает разные магазины. Следовательно, имеются две независимые друг от друга функции: ПРОИЗВОДСТВО и СНАБЖЕНИЕ (рис. 3.4), т. е. в отношении СБЫТ не выполняются F-зависимости ЗАВОДàTOBAP и ЗАВОДàМАГАЗИН. Однако это отношение без потери информации разлагается на два отношения: ПРОИЗВОДСТВО (табл. 3.8) и СНАБЖЕНИЕ (табл. 3.9).

Рассмотрим отношение СБЫТ1 с такой же схемой (табл. 3.7).

Рис. 3.4. Функция отношения СБЫТ

Таблица 3.7. Отношение СБЫТ

Таблица 3.8. Производство

Таблица 3.9. Снабжение

Таблица 3.10. Отношение СБЫТ1

Разложив это отношение на схемы ПРОИЗВОДСТВО (ЗАВОД ТОВАР) и СНАБЖЕНИЕ (ЗАВОД МАГАЗИН), снова получим соответствующие проекции в табл. 3.8 и 3.9. Однако соединение данных проекций не восстанавливает исходного отношения, так как появляется кортеж <z₁ t₂ m₂>

Проанализируем, какими же свойствами отличаются отношения СБЫТ и СБЫТ1. В первом случае если некоторый товар, например t₂, производится заводом, например z₁, то он поставляется во все магазины, а во втором случае — нет. В действительности, если завод z₁ начинает снабжать новый магазин m₃, то в отношении СБЫТ нужно создать два новых кортежа: по одному для каждого товара. Это связано с взаимной независимостью двух функций (см. рис. 3.4) и лучше осуществляется с помощью двух проекций отношения СБЫТ.

Пусть R(A) —отношение, где А = {А₁, А₂,...,А_n}, X, У, Z — подмножества А. Имеет место многозначная зависимость в отношении R, которую обозначают XààY/Z, если при наличии в R кортежей <х у z> и <х у' z'> должны обязательно быть кортежи <х у' z> и <х у z'>.

Так, для рассмотренного выше отношения СБЫТ имеем

ЗАВОДàà ТОВАР/МАГАЗИН, что означает:

если завод производит товар, то он поставляется во все магазины, которые снабжаются заводом;

если завод снабжает некоторый магазин, то магазину поставляются все товары, производимые заводом;

все товары, производимые заводом, продаются мага­зинами, которые снабжаются заводом.

Пусть R(A) - реляционная схема, X, У - непересекающиеся подмножества A, Z = A - (X, У). Отношение R удовлетворяет многозначной зависимости (MV-зависимости), если для любых кортежей t₁ и t₂ из R, для которых t₁(X)=t₂(X), в R существует кортеж t₃, для которого t₃(Х) = t₁(Х), t₃(У)=t₁(У), t₃(Z)=t₂(Z). Из симметрии определения относительно t₁ и t₂ получаем, что в R имеется также кортеж t₄, для которого t₄(X)=t₁{X), t₄(Y)=t₂{Y) и t₄(Z) = t₁{Z). Из определения MV-зависимости вытекает следующее утверждение.

Утверждение. Если отношение r(R) удовлетворяет MV-зависимости XààY и Z = R—{X, Y), то r удовлетворяет XààY

В определении MV-зависимости XààY требуется, чтобы ее левая и правая части различались, т. е. чтобы пересечение X и Y было пустым. Для этого есть две причины: во-первых, свойство транзитивности не всегда выполняется, если снято ограничение, и, во-вторых, проектировщик использует на практике MV-зависимости с непересекающимися множествами атрибутов.

Предположим, что в определении MV-зависимости XààY пересечение X и Y не является пустым, т. е. отношение r(R) удовлетворяет XààY и Y' = Y — X. Тогда r(R) удовлетворяет XààY. Действительно, в соответствии с определением MV-зависимости XààY найдутся кортежи t₁ и t₂, для которых t₁ (X) = t₂ (X), и должен быть кортеж t₃, для которого t₃{X) = t₁(X), t₃(Y) =t₁(Y), t₃(Z)=t₂(Z). Но если t₃(Y) = t₁(У), то t₃(Y')= t₁(Y'), так как У' ≤Y. Итак, r удовлетворяет XààY'.

Предположим, что пересечение X и У пусто и отношение r(R) удовлетворяет ХààY. Если X' Y, то X àà YХ' согласно модифицированному определению MV-зависимости; если t₁, t₂ принадлежит r и t₁ (X) = t₂ (X) существует кортеж t₃, для которого t₃ (X) = t₁ (X), t₃ (Y) = t₁(Y), t₃ (Z) = t₂ (Z). Следовательно, t₃ (YX') = t₁ (YX').

Связь MV-зависимости с декомпозициями без потерь можно выразить следующим утверждением.

Утверждение. Пусть r(R) —отношение, X, Y, Z — подмножества из R такие, что Z=R—{XY). Отношение r удовлетворяет MV-зависимости Хàà У тогда и только тогда, когда r без потери информации разлагается на отношения со схемами R₁ = XY и R₂ = XZ.

Для проверки выполнимости XààY в отношении r его нужно спроектировать на XY и X(R—XY), соединить и результат сравнить с r. Можно проверить MV-зависимость, не используя проектирования и соединения, а только сортировку и подсчет. Пусть Z = R—(XY), R₁ = XY, R₂ = XZ. Если r₁ =π_R1(r) и r₂ =π_R2(r), то r₁ ∞ r₂ всегда содержит r. Пусть, далее, для некоторого x, принадлежащего Х, существует с₁ кортежей в r₁ и с₂ кортежей в r₂ со значением х. Пусть с — число таких кортежей в r. Если для любого x, принадлежащего Х, c=c₁×c₂ , то r=r₁ ∞ r₂