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

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

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

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

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

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

Нехай R схема відношення і нехай \alpha \subseteq R і \beta \subseteq R (підмножини). Багатозначна залежність
\alpha \twoheadrightarrow \beta
(що можна прочитати як  \alpha багатовизначає  \beta ) виконується на R якщо, в будь-якому допустимому віднощенні r(R), для всіх пар кортежів t_1 і t _2 в r таких, що t _1[\alpha]=t _2[\alpha], існують кортежі t _3 і t _4 в r таких, що
t _1[\alpha] = t _2 [\alpha] = t _3 [\alpha] = t _4 [\alpha]
t _3[\beta] = t _1 [\beta]
t _3[R - \beta] = t _2 [R - \beta]
t _4[\beta] = t _2 [\beta]
t _4[R - \beta] = t _1 [R - \beta]

Простіше попередні умови можна виразити так: якщо ми позначимо (x,y,z) кортеж із значеннями для \alpha, \beta, R - \alpha - \beta рівними x, y, z, відповідно тоді, коли кортежі (a,b,c) і (a,d,e) існують в r, кортежі (a,b,e) і (a,d,c) мають також існувати в r.

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

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

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

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

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

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

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

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

  • Якщо \alpha \twoheadrightarrow \beta, тоді \alpha \twoheadrightarrow R - \beta (див. лему Феджина)
  • Якщо \alpha \twoheadrightarrow \beta i \gamma \subseteq \delta, тоді \alpha \delta \twoheadrightarrow \beta \gamma
  • Якщо \alpha \twoheadrightarrow \beta i \beta \twoheadrightarrow \gamma, тоді \alpha \twoheadrightarrow \gamma - \beta

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

  • Якщо \alpha \rightarrow \beta, тоді \alpha \twoheadrightarrow \beta
  • Якщо \alpha \twoheadrightarrow \beta i \beta \rightarrow \gamma, тоді \alpha \rightarrow \gamma - \beta

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

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

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

У відношенні r\left( A,B,C \right) виконується багатозначна залежність A\twoheadrightarrow B тоді і тільки тоді, коли вірно A\twoheadrightarrow C.

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

Нехай дане відношення r\left( A,B,C \right). Відношення r дорівнює поєднанн. його проекцій будет равно соединению его проекций r\left[ A,B \right] і r\left[ A,C \right] тоді і тільки тоді, коли для відношення r виконується нетривіальна багатозначна залежність A\twoheadrightarrow B|C.

\left( r\left( A,B,C \right)=r\left[ A,B \right]\ \text{JOIN}\ r\left[ A,C \right] \right)\Leftrightarrow \left( A\twoheadrightarrow B|C \right)

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

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

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

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

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

Залежність, що явно вимагає присутність певних кортежів у відношенні.
Наприклад, розглянемо такі відношення: ENROLLS(studentId, name, course), PERFORM(studentId, course, grade).
І таке обмеження цілісності: кожен студент, що бере участь в якомусь курсі отримує оцінку. Це приклад залежності включення (англ. inclusion dependency); позначимо її як ENROLLS[studentId, course]\subseteq PERFORM[studentId, course].
Тотожною до нашого обмеження цілісності формулою реляційного числення буде:
\forall x, y, z (ENROLLS(x,y,z)) \rightarrow \exists w PERFORM(x, z, w)) це приклад кортеж-твірної залежності.

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

Багатозначна залежність, що залучає всі атрибути відношення тобто R = \alpha \cup \beta. Тривіальна багатозначна залежність означає, для кортежів t_1 і t _2, кортежі t _3 і t _4 дорівнюють t_1 і t _2.

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

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

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

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

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