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

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

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

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

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

Нехай $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 \to \beta$, тоді $\alpha \twoheadrightarrow \beta$
• Якщо $\alpha \twoheadrightarrow \beta$ i $\beta \to \gamma$, тоді $\alpha \to \gamma -\beta$

Застосування

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

Лема Фейджина

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

Теорема Фейджина

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

$(r(A,B,C)=r[A,B]\text{JOIN}r[A,C])\iff (A\twoheadrightarrow B|C)$

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

Визначення

повне обмеження (Шаблон:Lang-en):

Це обмеження, що виражає що-небудь про всі атрибути в базі даних (на відміну від вбудованого обмеження (Шаблон:Lang-en)). Те, що багатозначні залежності є повними обмеженнями випливає з його визначення, оскільки воно стверджує дещо про атрибути $R-\beta$.

кортеж-твірна залежність (Шаблон:Lang-en):

Залежність, що явно вимагає присутність певних кортежів у відношенні.

Наприклад, розглянемо такі відношення: $ENROLLS(studentId,name,course),$ $PERFORM(studentId,course,grade).$

І таке обмеження цілісності: кожен студент, що бере участь в якомусь курсі отримує оцінку. Це приклад залежності включення (Шаблон:Lang-en); позначимо її як $ENROLLS[studentId,course]\subseteq PERFORM[studentId,course].$

Тотожною до нашого обмеження цілісності формулою реляційного числення буде:

$\mathrm{\forall }x,y,z(ENROLLS(x,y,z))\to \mathrm{\exists }wPERFORM(x,z,w))$, що є прикладом кортеж-твірної залежності.

тривіальна багатозначна залежність 1 (Шаблон:Lang-en):

Багатозначна залежність, що залучає всі атрибути відношення, тобто $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