Многозначные зависимости и четвертая нормальная форма

Аномалии в НФБК

Рассмотрим следующий пример:

Course	Lecturer	Book
СУБД	Корнеев Г. А.	Дейт
СУБД	Корнеев Г. А.	Ульман
Мат.Ан.	Кохась К. П.	Фихтенгольц
Мат.Ан.	Виноградов О. Л.	Фихтенгольц

В данном отношении подразумевается, что набор книг по курсу не зависит от преподавателя.

Тогда все атрибуты будут ключевыми: у курса и лектора бывает много книг, лектор может рекомендовать книгу по нескольким курсам, книгу для курса могут рекомендовать все лекторы этого курса. Поэтому здесь присутствуют только тривиальные функциональные зависимости, поэтому отношение находится в нормальной форме Бойса-Кодда.

При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будут все 3 вида аномалии:

• Вставки: невозможно указать литературу по курсу без преподавателя.
• Удаления: нельзя удалить преподавателя, не потеряв литературу по курсу.
• Изменения: если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.

Для таких случаев было введено понятие многозначной зависимости.

Многозначная зависимость

Определение:

[math]X \twoheadrightarrow Y[/math] [math](X[/math] многозначно определяет [math]Y)[/math] в отношении [math]R:[/math] [math]X[/math] и [math]Y - [/math] множества атрибутов Множество значений [math]Y[/math] не зависит от [math]R \setminus X \setminus Y[/math] [math]\forall x,y1,z1,y2,z2[/math] если [math](x,y1,z1)∈R[/math] и [math](x,y2,z2) \in R[/math] то [math]{y{|}(x,y,z1) \in R}={y{|}(x,y,z2) \in R}[/math]

Утверждение:

Любая функциональная зависимость является множественной зависимостью.

[math]\triangleright[/math]

У $Y$ при фиксированном $X$ есть ровно одно значение. То есть мощность множества, которое зависит, равна одному.

[math]\triangleleft[/math]

Теорема Фейгина

Теорема:

Обобщение теоремы Хита: [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y [/math]

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] [math]R(XYZ)=\pi_{XY}(R) \bowtie \pi_{XZ}(R) \Rightarrow (x,y,z) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)[/math] Пусть [math](x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R),[/math] тогда [math](x,y,z1) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R) \Leftrightarrow (x,y,z2) \in R[/math] [math]\Leftarrow[/math] [math]\forall(x,y,z) \in \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Rightarrow (x,y) \in \pi_{XY}(R)\wedge(x,z) \in \pi_{XY}(R)[/math] Тогда [math]\exists y',z':(x,y',z) \in R\wedge(x,y,z') \in R[/math] Так как [math]X \twoheadrightarrow Y, то (x,y,z) \in R \wedge (x,y',z') \in R [/math]

[math]\triangleleft[/math]

В отличие от теоремы Хита, где доказывалась только достаточность, в теореме Фейгина доказывается необходимость и достаточность.

Теорема о дополнении

Теорема:

[math]R(XYZ)[/math] и [math]X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z[/math]

Доказательство:

[math]\triangleright[/math]

Из [math]X \twoheadrightarrow Y[/math] по теореме Фейгина следует [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).[/math] Вследствие коммутативности [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) = \pi_{XZ}(R) \bowtie \pi_{XY}(R).[/math] Применяя еще раз теорему Фейгина, получаем, что [math]X \twoheadrightarrow Z.[/math]

[math]\triangleleft[/math]

[math]X \twoheadrightarrow Y {|} Z[/math] обозначается: [math]X[/math] множественно определяет [math]Y[/math] и [math]Z[/math].

Утверждение:

[math]\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset[/math]

[math]\triangleright[/math]

Докажем от противного. Попробуем доказать, что данное утверждение неверно. По определению для того, чтобы доказать, что множественная зависимость отсутствует, необходимо взять [math]X[/math], найти к нему два различных [math]Z[/math] таких, что множества [math]Y[/math] будут разные. Однако два различных [math]Z[/math] в пустом множестве мы найти не можем. Итого, если одно из множеств пусто, то такая соответствующая множественная зависимость тривиальна, выполняется для всех отношений.

[math]\triangleleft[/math]

Определение:

[math]X \twoheadrightarrow Y{|}\emptyset[/math] называется тривиальной множественной зависимостью.

Четвертая нормальная форма

Определение:

Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда Для каждой нетривиальной множественной зависимости [math]X \twoheadrightarrow Y {|} Z [/math] и атрибута [math]A: X \rightarrow A[/math] Для каждой нетривиальной множественной зависимости [math]X \twoheadrightarrow Y{|}Z: X[/math] – надключ Каждая нетривиальная множественная зависимость является функциональной зависимостью и отношение находится в нормальной форме Бойса-Кодда

Достижимость

Теорема:

Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ

Доказательство:

[math]\triangleright[/math]

Пока есть множественная зависимость, декомпозируем на два отношения. Количество атрибутов в каждом отношении всегда уменьшается. в конце останутся либо отношения из одного атрибута, которые находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению

[math]\triangleleft[/math]

Пример приведения к 4НФ

Пусть задано отношение:

Course	Lecturer	Book
СУБД	Корнеев Г. А.	Дейт
СУБД	Корнеев Г. А.	Ульман
Мат.Ан.	Кохась К. П.	Фихтенгольц
Мат.Ан.	Виноградов О. Л.	Фихтенгольц

В данном отношении есть множественная зависимость: [math]Course \twoheadrightarrow Lecturer {|} Book[/math], поэтому декомпозируем его следующим образом:

Course	Lecturer
СУБД	Корнеев Г. А.
СУБД	Корнеев Г. А.
Мат.Ан.	Кохась К. П.
Мат.Ан.	Виноградов О. Л.

Course	Book
СУБД	Дейт
СУБД	Ульман
Мат.Ан.	Фихтенгольц
Мат.Ан.	Фихтенгольц