Багатозначна залежність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії баз даних, багатозначна залежність — повне обмеження між двома множинами атрибутів у відношенні.

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

Формальне визначення[ред.ред. код]

Формальне визначення наступне. [1]

Нехай схема відношення і нехай і (підмножини). Багатозначна залежність

(що можна прочитати як багатовизначає ) виконується на якщо, в будь-якому допустимому віднощенні , для всіх пар кортежів і в таких, що , існують кортежі і в таких, що





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

Приклад[ред.ред. код]

Уявімо такий приклад бази даних курсів, книжки рекомендовані для кожного курсу, викладачі, які читають курс:

Викладання
Курс Книга Викладач
МатАн Фіхтенгольц Паламарчук Д
МатАн Пасічник Сироватка І
МатАн Фіхтенгольц Сироватка І
МатАн Пасічник Паламарчук Д
МатАн Фіхтенгольц Негода В
МатАн Пасічник Негода В
Дискретка Нікольський Паламарчук Д
Дискретка Нікольський Сироватка І

Через те, що викладачі прикріплені до курсу і книги прикріплені до курсу незалежні між собою, такий дизайн бази даних містить багатозначну залежність; якщо б нам довелось додати книгу до курсу МатАн, ми мали б по одному запису для кожного викладача цього кусу і навпаки, це і є повна залежність.

Скажемо формально, тут присутні дві багатозначні залежності: {курс}  {книга} і тотожно {курс}  {викладач}.

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

Оптимальним розв'язком проблеми буде декомпозиція відношення на два із заголовками {Курс , Книга} и {Курс , Викладач}. Така декомпозиція буде знаходитися в 4НФ. Допустимість декомпозиції встановлює теорема Феджина.

Цікаві властивості[ред.ред. код]

  • Якщо , тоді (див. лему Феджина)
  • Якщо i , тоді
  • Якщо i , тоді

Наступні також залучають функціональну залежність:

  • Якщо , тоді
  • Якщо i , тоді

Застосування[ред.ред. код]

Декомпозиція відношень[ред.ред. код]

Лема Фейджина[ред.ред. код]

У відношенні виконується багатозначна залежність тоді і тільки тоді, коли вірно .

Теорема Фейджина[ред.ред. код]

Нехай дане відношення . Відношення дорівнює поєднанн. його проекцій будет равно соединению его проекций і тоді і тільки тоді, коли для відношення виконується нетривіальна багатозначна залежність .

Ця теорема є суворішою версією теореми Хіта.

Визначення[ред.ред. код]

повне обмеження (англ. full constraint):

Обмеження, яке виражає що-небудь про всі атрибути в базі даних. (На відміну від вбудованого обмеження (англ. embedded constraint).) Те, що багатозначні залежності є повними обмеженнями випливає з його визначення, бо воно каже щось про атрибути .

кортеж-твірна залежність (англ. tuple-generating dependency):

Залежність, що явно вимагає присутність певних кортежів у відношенні.
Наприклад, розглянемо такі відношення:
І таке обмеження цілісності: кожен студент, що бере участь в якомусь курсі отримує оцінку. Це приклад залежності включення (англ. inclusion dependency); позначимо її як
Тотожною до нашого обмеження цілісності формулою реляційного числення буде:
це приклад кортеж-твірної залежності.

тривіальна багатозначна залежність 1 (англ. trivial multivalued dependency):

Багатозначна залежність, що залучає всі атрибути відношення тобто . Тривіальна багатозначна залежність означає, для кортежів і , кортежі і дорівнюють і .

тривіальна багатозначна залежність 2

Багатозначна залежність для якої .

Примітки[ред.ред. код]

  1. Silberschatz, Abraham; Korth, Sudarshan (2006). Database System Concepts (вид. 5th). McGraw-Hill. с. 295. ISBN 007-124476-X. 

Посилання[ред.ред. код]