ЗАМИКАННЯ МНОЖИНИ ЗАЛЕЖНОСТЕЙ

Як згадувалося вище, з одних функціональних залежностей можуть слідувати інші функціональні залежності Наприклад, розглянемо наведену нижче залежність

{S #, Р #} → {CITY, QTY}

З неї випливають наведені нижче функціональні залежності

{S #, Р #} →

CITY {   S#,    P#   }

→ QTY

У якості більш складного приклад можна привести змінну відносини R з атрибутами А, в і С, для яких виконуються функціональні залежності А → в і В → С Неважко помітити, що в цьому випадку також виконується функціональна залежність А B і C с, яка називається транзитивної функціональною залежністю, тобто з залежить від А транзитивно, або проходячи через в

Безліч всіх функціональних залежностей, які слідують із заданої множини функціональних залежностей s, називається замиканням безлічі s і позначається символом S + (необхідно враховувати те, що воно не має нічого спільного з поняттям замикання, яке розглядається в реляційної алгебри) З наведеного визначення випливає, що для вирішення сформульованої задачі необхідно знайти алгоритм обчислення S + на основі S Перша спроба вирішити цю проблему була зроблена в статті Армстронга (Armstrong) [112], в якій автор запропонував набір правил виводу нових функціональних залежностей на основі заданих (ці правила також часто називають аксіомами Армстронга) Ці правила виведення можуть формулюватися різними способами, з яких найпростішим є наступний Нехай А, в і С – довільні підмножини множини атрибутів заданої змінної відносини R Домовимося також, що символічна запис АВ означає обєднання множин А І В Тоді правила виведення визначаються наступним чином

1 Правило рефлексивності Якщо безліч в є підмножиною множини А,

ТО А→   В

2 Правило доповнення Якщо А → B, то АС → ВС

3 Правило транзитивності Якщо А → B і B → C, то А → С

Кожне з цих трьох правил може бути безпосередньо доведено на основі визначення функціональної залежності (безумовно, перше з них – це просто саме визначення тривіальної залежності) Більш того, ці правила є повними в тому сенсі, що для заданої множини функціональних залежностей s мінімальний набір функціональних залежностей, які мають на увазі всі залежності з безлічі S, може бути виведений з ФЗ безлічі s на основі лише цих правил Вони є також несуперечливими, оскільки з їх допомогою не можуть бути виведені ніякі додаткові функціональні залежності (тобто залежності, що не обумовлені функціональними залежностями безлічі S) Інакше кажучи, ці правила можуть використовуватися для отримання замикання S +

З метою спрощення завдання практичного обчислення замикання S +, з трьох наведених вище правил можна вивести кілька додаткових правил (Надалі передбачається, що D – це ще одне довільне підмножина безлічі атрибутів R)

4 Правило самовизначення А → А

5 Правило декомпозиції Якщо А → Нд, то А → Bі A → C

6 Правило обєднання Якщо А → В І А → С, то А → ВС

7 Правило композиціїЯкщо А → B і С → D, то АС → BD

Крім того, Дарвен (Darwen) у своїй роботі [117] довів наступне правило, яке він назвав загальної теоремою обєднання

8 Якщо А → B і C → D, то А ∪ (С В) → BD (тут символ ∪ позначає операцію обєднання множин, а символ – – Операцію різниці множин)

Назва загальна теорема обєднання вказує на те, що деякі з перерахованих вище правил можуть бути виведені як окремі випадки цієї теореми [117]

Приклад Нехай дана деяка змінна відношення R з атрибутами А, В, С, D, E, F і наступними функціональними залежностями

А →   НД У→   Е CD

EF

Зверніть увагу, що спосіб запису був трохи доповнений (без шкоди для змісту) наприклад, символи НД означають безліч, що складається з атрибутів B і C, хоча раніше вони означали обєднання B і C, де B і C були множинами атрибутів

Примітка Якщо необхідно, то цьому прикладу можна надати більш конкретний зміст, а саме: А-особистий номер співробітника, в – номер відділу, с – особистий номер керівника (начальника) даного співробітника, D-номер проекту, очолюваного даними керівником (унікальний для кожного окремо взятого керівника), Е – назва відділу, F – кількість часу, що приділяється даними керівником зазначеного проекту

Тепер можна показати, що для змінної відносини R виконується також функціональна залежність AD → F, яка внаслідок цього належить до замикання заданої множини функціональних залежностей

1 А → BC (Дано)

2 А → C (Слід з п 1 згідно з правилом декомпозиції)

3 AD → CD (Слід з п 2 згідно з правилом доповнення)

4 CD → EF (Дано)

5 AD → EF (Слід з пп 3 і 4 згідно з правилом транзитивності)

6 AD → F (Слід з п 5 згідно з правилом декомпозиції)

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*