Навігація
Головна
 
Головна 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, C o [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, де WY і 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
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук