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

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

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

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

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

Нехай $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$.

Посилання

• Multivalued dependencies and a new Normal form for Relational Databases (PDF) - Ronald Fagin, IBM Research Lab