Изменения
Новая страница: «== Аномалии в НФБК == Рассмотрим следующий пример: {| class="wikitable" ! Course !! Lecturer !! Book |- | СУБД || Ко…»
== Аномалии в НФБК ==
Рассмотрим следующий пример:
{| class="wikitable"
! Course !! Lecturer !! Book
|-
| СУБД || Корнеев Г. А. || Дейт
|-
| СУБД || Корнеев Г. А. || Ульман
|-
| Мат.Ан. || Кохась К. П. || Фихтенгольц
|-
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
|}
Здесь присутствуют только тривиальные функциональные зависимости, поэтому отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]].
При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будет все 3 вида аномалии:
* '''Вставки''': невозможно указать литературу по курсу без преподавателя.
* '''Удаления''': нельзя удалить преподавателя, не потеряв литературу по курсу.
* '''Изменения''': если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.
== Многозначная зависимость ==
{{Определение
|definition=
<tex>X \twoheadrightarrow Y</tex> <tex>(X</tex> многозначно определяет <tex>Y)</tex> в отношении <tex>R:</tex>
* <tex>X</tex> и <tex>Y - </tex> множества атрибутов
* Множество значений <tex>Y</tex> не зависит от <tex>R \setminus X \setminus Y</tex>
* <tex>\forall x,y1,z1,y2,z2</tex> если <tex>(x,y1,z1)∈R</tex> и <tex>(x,y2,z2) \in R</tex> то <tex>{y{|}(x,y,z1) \in R}={y{|}(x,y,z2) \in R}</tex>
}}
{{Утверждение
|statement=
Любая [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональная зависимость]] является множественной зависимостью.
}}
=== Теорема Фейгина ===
{{Теорема
|statement= Обобщение [[Цели_и_средства_нормализации|теоремы Хита]]: <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y </tex>
|proof=
* <tex>\Rightarrow</tex>
**<tex>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)</tex>
**Пусть <tex>(x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R),</tex> тогда <tex>(x,y,z1) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R) \Leftrightarrow (x,y,z2) \in R</tex>
* <tex>\Leftarrow</tex>
** <tex>\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)</tex>
** Тогда <tex>\exists y',z':(x,y',z) \in R\wedge(x,y,z') \in R</tex>
** Так как <tex>X \twoheadrightarrow Y, то (x,y,z) \in R \wedge (x,y',z') \in R </tex>
}}
=== Теорема о дополнении ===
{{Теорема
|statement=<tex>R(XYZ)</tex> и <tex>X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z</tex>
|proof=
Из <tex>X \twoheadrightarrow Y</tex> по теореме Фейгина следует <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).</tex>
Вследствие коммутативности <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) = \pi_{XZ}(R) \bowtie \pi_{XY}(R).</tex>
Применяя еще раз теорему Фейгина, получаем, что <tex>X \twoheadrightarrow Z.</tex>
}}
<tex>X \twoheadrightarrow Y {|} Z</tex> обозначается: <tex>X</tex> множественно определяет <tex>Y</tex> и <tex>Z</tex>.
'''Следствие.''' <tex>\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset</tex>
<tex>X \twoheadrightarrow Y{|}\emptyset</tex> называется тривиальной множественной зависимостью.
== Четвертая нормальная форма ==
{{Определение
|definition=
Отношение находится в '''четвертой нормальной форме''' (4НФ) тогда и только тогда, когда
* Для каждой нетривиальной множественной зависимости <tex>X \twoheadrightarrow Y {|} Z </tex> и атрибута <tex>A: X \rightarrow A</tex>
* Для каждой нетривиальной множественной зависимости <tex>X \twoheadrightarrow Y{|}Z: X</tex> – надключ
* Каждая нетривиальная множественная зависимость является [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональной зависимостью]] и отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]]
}}
=== Достижимость ===
{{Теорема
|statement=Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
|proof=
* Пока есть множественная зависимость, декомпозируем на два отношения.
* Количество атрибутов в каждом отношении всегда уменьшается.
* в конце останутся либо отношения из одного атрибута, которое находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению
}}
=== Приведение к 4НФ ===
Пусть задано отношение:
{| class="wikitable"
! Course !! Lecturer !! Book
|-
| СУБД || Корнеев Г. А. || Дейт
|-
| СУБД || Корнеев Г. А. || Ульман
|-
| Мат.Ан. || Кохась К. П. || Фихтенгольц
|-
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
|}
В данном отношении есть множественная зависимость: <tex>Course \twoheadrightarrow Lecturer {|} Book</tex>, поэтому декомпозируем его следующим образом:
{| class="wikitable"
! Course !! Lecturer
|-
| СУБД || Корнеев Г. А.
|-
| СУБД || Корнеев Г. А.
|-
| Мат.Ан. || Кохась К. П.
|-
| Мат.Ан. || Виноградов О. Л.
|}
{| class="wikitable"
! Course !! Book
|-
| СУБД || Дейт
|-
| СУБД|| Ульман
|-
| Мат.Ан. || Фихтенгольц
|-
| Мат.Ан. || Фихтенгольц
|}
Рассмотрим следующий пример:
{| class="wikitable"
! Course !! Lecturer !! Book
|-
| СУБД || Корнеев Г. А. || Дейт
|-
| СУБД || Корнеев Г. А. || Ульман
|-
| Мат.Ан. || Кохась К. П. || Фихтенгольц
|-
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
|}
Здесь присутствуют только тривиальные функциональные зависимости, поэтому отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]].
При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будет все 3 вида аномалии:
* '''Вставки''': невозможно указать литературу по курсу без преподавателя.
* '''Удаления''': нельзя удалить преподавателя, не потеряв литературу по курсу.
* '''Изменения''': если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.
== Многозначная зависимость ==
{{Определение
|definition=
<tex>X \twoheadrightarrow Y</tex> <tex>(X</tex> многозначно определяет <tex>Y)</tex> в отношении <tex>R:</tex>
* <tex>X</tex> и <tex>Y - </tex> множества атрибутов
* Множество значений <tex>Y</tex> не зависит от <tex>R \setminus X \setminus Y</tex>
* <tex>\forall x,y1,z1,y2,z2</tex> если <tex>(x,y1,z1)∈R</tex> и <tex>(x,y2,z2) \in R</tex> то <tex>{y{|}(x,y,z1) \in R}={y{|}(x,y,z2) \in R}</tex>
}}
{{Утверждение
|statement=
Любая [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональная зависимость]] является множественной зависимостью.
}}
=== Теорема Фейгина ===
{{Теорема
|statement= Обобщение [[Цели_и_средства_нормализации|теоремы Хита]]: <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y </tex>
|proof=
* <tex>\Rightarrow</tex>
**<tex>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)</tex>
**Пусть <tex>(x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R),</tex> тогда <tex>(x,y,z1) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R) \Leftrightarrow (x,y,z2) \in R</tex>
* <tex>\Leftarrow</tex>
** <tex>\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)</tex>
** Тогда <tex>\exists y',z':(x,y',z) \in R\wedge(x,y,z') \in R</tex>
** Так как <tex>X \twoheadrightarrow Y, то (x,y,z) \in R \wedge (x,y',z') \in R </tex>
}}
=== Теорема о дополнении ===
{{Теорема
|statement=<tex>R(XYZ)</tex> и <tex>X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z</tex>
|proof=
Из <tex>X \twoheadrightarrow Y</tex> по теореме Фейгина следует <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).</tex>
Вследствие коммутативности <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) = \pi_{XZ}(R) \bowtie \pi_{XY}(R).</tex>
Применяя еще раз теорему Фейгина, получаем, что <tex>X \twoheadrightarrow Z.</tex>
}}
<tex>X \twoheadrightarrow Y {|} Z</tex> обозначается: <tex>X</tex> множественно определяет <tex>Y</tex> и <tex>Z</tex>.
'''Следствие.''' <tex>\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset</tex>
<tex>X \twoheadrightarrow Y{|}\emptyset</tex> называется тривиальной множественной зависимостью.
== Четвертая нормальная форма ==
{{Определение
|definition=
Отношение находится в '''четвертой нормальной форме''' (4НФ) тогда и только тогда, когда
* Для каждой нетривиальной множественной зависимости <tex>X \twoheadrightarrow Y {|} Z </tex> и атрибута <tex>A: X \rightarrow A</tex>
* Для каждой нетривиальной множественной зависимости <tex>X \twoheadrightarrow Y{|}Z: X</tex> – надключ
* Каждая нетривиальная множественная зависимость является [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональной зависимостью]] и отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]]
}}
=== Достижимость ===
{{Теорема
|statement=Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
|proof=
* Пока есть множественная зависимость, декомпозируем на два отношения.
* Количество атрибутов в каждом отношении всегда уменьшается.
* в конце останутся либо отношения из одного атрибута, которое находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению
}}
=== Приведение к 4НФ ===
Пусть задано отношение:
{| class="wikitable"
! Course !! Lecturer !! Book
|-
| СУБД || Корнеев Г. А. || Дейт
|-
| СУБД || Корнеев Г. А. || Ульман
|-
| Мат.Ан. || Кохась К. П. || Фихтенгольц
|-
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
|}
В данном отношении есть множественная зависимость: <tex>Course \twoheadrightarrow Lecturer {|} Book</tex>, поэтому декомпозируем его следующим образом:
{| class="wikitable"
! Course !! Lecturer
|-
| СУБД || Корнеев Г. А.
|-
| СУБД || Корнеев Г. А.
|-
| Мат.Ан. || Кохась К. П.
|-
| Мат.Ан. || Виноградов О. Л.
|}
{| class="wikitable"
! Course !! Book
|-
| СУБД || Дейт
|-
| СУБД|| Ульман
|-
| Мат.Ан. || Фихтенгольц
|-
| Мат.Ан. || Фихтенгольц
|}
