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

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

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

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

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

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