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

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

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

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

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

Нехай ${\displaystyle R}$ схема відношення і нехай ${\displaystyle \alpha \subseteq R}$ і ${\displaystyle \beta \subseteq R}$ (підмножини). Багатозначна залежність
${\displaystyle \alpha \twoheadrightarrow \beta }$
(що можна прочитати як ${\displaystyle \alpha }$ багатовизначає ${\displaystyle \beta }$) виконується на ${\displaystyle R}$ якщо, в будь-якому допустимому віднощенні ${\displaystyle r(R)}$, для всіх пар кортежів ${\displaystyle t_{1}}$ і ${\displaystyle t_{2}}$ в ${\displaystyle r}$ таких, що ${\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]}$, існують кортежі ${\displaystyle t_{3}}$ і ${\displaystyle t_{4}}$ в ${\displaystyle r}$ такі, що
${\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]=t_{3}[\alpha ]=t_{4}[\alpha ]}$
${\displaystyle t_{3}[\beta ]=t_{1}[\beta ]}$
${\displaystyle t_{3}[R-\beta ]=t_{2}[R-\beta ]}$
${\displaystyle t_{4}[\beta ]=t_{2}[\beta ]}$
${\displaystyle t_{4}[R-\beta ]=t_{1}[R-\beta ]}$

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

Приклад

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

Викладання

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

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

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

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

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

Цікаві властивості

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

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

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

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

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

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

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

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

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

${\displaystyle \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)). Те, що багатозначні залежності є повними обмеженнями випливає з його визначення, оскільки воно стверджує дещо про атрибути ${\displaystyle R-\beta }$.

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

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

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

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

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

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

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

Багатозначна залежність, що залучає всі атрибути відношення, тобто ${\displaystyle R=\alpha \cup \beta }$. Тривіальна багатозначна залежність означає, що для кортежів ${\displaystyle t_{1}}$ і ${\displaystyle t_{2}}$, кортежі ${\displaystyle t_{3}}$ і ${\displaystyle t_{4}}$ дорівнюють ${\displaystyle t_{1}}$ і ${\displaystyle t_{2}}$.

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

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