asyan.org
добавить свой файл
1
Лекція №9

Тема: Функціональні залежності
План

  1. Функціональна залежність (ФЗ).

  2. Тривіальні і нетривіальні залежності.

  3. Аксіоми Армстронга.

  4. Неприводиме множина залежностей.

  5. Нормалізація відносин.


Функціональна залежність (ФЗ) є зв'язком типу багато до одного між безліччю атрибутів усередині даного відношення.

Поняття функціональної залежності визначається з розділенням функціональних залежностей на виконувані в деяких окремих випадках і виконувані завжди.

^ Основні визначення. Використовуємо розширену версію відношення SP для демонстрації основних ідей даного розділу. На додаток до звичних атрибутів S#,Р# і QTY додамо атрибут СIТY, що представляє місто відповідного постачальника. Змінене відношення назвемо SCP (мал. 1).

Для будь-якого відношення розрізняються:

а) значення цього відношення (тобто значення змінної відношення) в певний момент часу;

б) набір всіх можливих значень, які дане відношення (змінна) може приймати в різні моменти часу.

Визначення 1. Хай Х і У - довільні підмножини безлічі атрибутів відношення R. У функціонально залежно від X (позначається XУ і читається або як "X функціонально визначає У", або як "X стрілка У"), тоді і тільки тоді, коли кожне значення підмножини X відношення R зв'язане в точності з одним значенням підмножини У відношення R.

Інакше кажучи, якщо два кортежі відношення R співпадають по значенню X, вони також співпадають і по значенню У.

Визначення 2. Ліва частина символічного запису функціональної залежності називається детермінантом.

Визначення 3. Права частина символічного запису функціональної залежності називається залежною частиною.

Детермінант і залежна частина є безліччю атрибутів. Коли множина містить тільки один атрибут, він називається одноелементною множиною.

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

Визначення 4. Хай R - змінна відношення, а Х і У - довільні підмножини безлічі атрибутів відношення R. У функціонально залежить від X (позначається XУ і читається або як "X функціонально визначає У", або як "X стрілка У"), тоді і тільки тоді, коли для будь-якого допустимого значення відношення R кожне значення підмножини X зв'язане в точності з одним значенням підмножини У.

^ Тривіальні і нетривіальні залежності. Одним із способів скорочення розміру множини ФЗ є виключення тривіальних залежностей, тобто таких, які не можуть не виконуватися. Залежність {S#,P#}{S#} для відношення SCP є тривіальною.

Визначення 5. ФЗ тривіальна тоді і тільки тоді, коли права частина є підмножиною (не обов'язково власним) лівої частини.

Визначення 6. Безліч всіх ФЗ, які задаються даним безліччю функціональних залежностей S, називається замиканням S і позначається символом S+.

Армстронгом (Armstrong) представлений набір правил висновку функціональних залежностей на основі заданих залежностей (ці правила називаються аксіомами Армстронга).

У перерахованих нижче правилах А, В і С - довільні підмножини безлічі атрибутів заданого відношення R, а символічний запис АВ означає об'єднання А і В.

Правило 1. Рефлексія: якщо В є підмножиною А, то АВ.

Правило 2. Доповнення: якщо АВ, то АСВС.

Правило 3. Транзитивність: якщо АВ і ВС, то АС.

Правило 4. Самовизначення: А А.

Правило 5. Декомпозиція: якщо АВС, то АВ і АС.

Правило 6. Об'єднання: якщо АВ і АС, то АВС.

Правило 7. Композиція: якщо АВ і СD, то АСBD.

Крім того, Дарвеном (Darwen) доведено правило, яке називається теоремою загального об'єднання.

Правило 8. Якщо АВ і СD, то А(С - В)BD (де символ " " позначає об'єднання множин, а символ "-" - їх різниця).

^ Замикання множини атрибутів. Не менш важливої є задача з'ясування, чи є підмножина атрибутів потенційним ключем відносини.

Визначення 7. Суперключем відносини R назвемо множину атрибутів відносини R, що містять у вигляді підмножини, (але не обов'язково власного) принаймні один потенційний ключ.

^ Неприводиме множина залежностей.

Нехай S1 і S2 є двома множинами ФЗ.

Визначення 8. Якщо будь-яка ФЗ, що є залежністю множини S1, також є залежністю множини S2, тобто якщо S1+  S2+, то S2 називається покриттям для S1. Це значить, що якщо накладають у СУБД обмеження представлені залежностями множини S2, то в цієї СУБД також накладені обмеження на основі залежностей множини S1.

Визначення 9. Якщо S2 - покриття для S1, а S1 - покриття для S2, тобто якщо S1+=S2+, то S1 і S2 еквівалентні.

Якщо S1 і S2 еквівалентні й накладені в СУБД обмеження представлені залежностями множини S2, то ці обмеження також можуть бути представлені залежностями множини S1. Вірно також і зворотне твердження.

Визначення 10. Множина ФЗ називається неприводимою тоді й тільки тоді, коли виконуються наступні три властивості.

Властивість 1. Права частина (залежна частина) кожної ФЗ множини S містить тільки один атрибут (тобто є одноелементною множиною).

Властивість 2. Ліва частина (детермінант) кожної ФЗ множини S є що не приводить, тобто жоден атрибут не може бути опущений з детермінанта без зміни замикання S+ (без конвертування множини S у деяку множину, не еквівалентне множині S). У такому випадку ФЗ є неприводи ліворуч.

Звойство 3. Жодна функціональна залежність в S не може бути опущена з S без зміни замикання S+ (тобто без конвертування множини S у деяку множину, не еквівалентне множині S).

Визначення 11. Множина залежносостей , що неприводимо й еквівалентно деякій іншій множині залежностей S, називається не приводить покрытием, що, множини S.

^ Нормалізація відносин

У загальному випадку нормалізація - це розбивка таблиці на дві або більше, що володіють кращими властивостями при включенні, зміні й видаленні даних. Остаточна мета нормалізації зводиться до одержання такого варіанта структури бази даних, у якому кожний факт з'являється лише в одному місці, тобто виключена надмірність інформації. Це робиться не стільки з метою економії пам'яті, скільки для виключення можливої суперечливості збережених даних.

^ Декомпозиція без втрат і функціональні залежності. Перш ніж приступати до розгляду процедури нормалізації, розглянемо роль функціональних залежностей для формулювання цієї концепції.

^ Визначення 12. Процедура нормалізації включає розбивку, або декомпозицію даного відношення на інші відносини, причому декомпозиція повинна бути оборотної, тобто виконуватися без втрат інформації.

Процес декомпозиції насправді є проектуванням. Таким чином, оператор декомпозиції в процедурі нормалізації фактично є оператором проектування.

Нижеследующая теорема_1(Хеза) установлює правило розбивки вихідного відношення на проекції.

Теорема 1. Нехай R{A, В, С} є відношенням, де А, В и С - атрибути цього відношення. Якщо R задовольняє залежності А( В, то R дорівнює з'єднанню його проекцій {А, В} і {А,С}.
Література:

Системы баз данных: Экон. Прил.: Учеб. Пособие / Андриенко В.Н., Берсуцкий Я.Г., Скобелев В.Г.,: Донецкий гос. Университет. – Донецк: ДонГУ, 1999. [4], 81-87

Контрольні запитання:

  1. Що називається функціональної залежністю (ФЗ)?

  2. Яка ФЗ називається тривіальною та нетривіальною?

  3. Що включає процедура нормалізації відношення?

  4. Коли множина ФЗ називається неприводимою?

  5. Аксіоми Армстронга.