Меню
Главная
УСЛУГИ
Авторизация/Регистрация
Реклама на сайте
 
Главная arrow Информатика arrow Базы данных
< Предыдущая   СОДЕРЖАНИЕ   Следующая >

Функциональные многозначные 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).

MV-зависимость

Рис. 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} не является навязанной.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика