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

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

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

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]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]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
СУБД	Дейт
СУБД	Ульман
Мат.Ан.	Фихтенгольц
Мат.Ан.	Фихтенгольц