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

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

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

Формальне визначення

Формальне визначення наступне. [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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.