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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о дополнении)
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 3 участников)
Строка 1: Строка 1:
== Аномалии в НФБК ==
+
== Мотивация. Аномалии в НФБК ==
  
 
Рассмотрим следующий пример:
 
Рассмотрим следующий пример:
Строка 13: Строка 13:
 
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
 
| Мат.Ан. || Виноградов О. Л. || Фихтенгольц
 
|}
 
|}
Здесь присутствуют только тривиальные функциональные зависимости, поэтому отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]].
+
В данном отношении подразумевается, что набор книг по курсу не зависит от преподавателя.
  
При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будет все 3 вида аномалии:
+
Тогда все атрибуты будут ключевыми: у курса и лектора бывает много книг, лектор может рекомендовать книгу по нескольким курсам, книгу для курса могут рекомендовать все лекторы этого курса.
 +
Поэтому здесь присутствуют только тривиальные функциональные зависимости, следовательно отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]].
 +
 
 +
При этом у нас будут все 3 вида аномалии:
 
* '''Вставки''': невозможно указать литературу по курсу без преподавателя.
 
* '''Вставки''': невозможно указать литературу по курсу без преподавателя.
 
* '''Удаления''': нельзя удалить преподавателя, не потеряв литературу по курсу.
 
* '''Удаления''': нельзя удалить преподавателя, не потеряв литературу по курсу.
 
* '''Изменения''': если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.
 
* '''Изменения''': если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.
 +
 +
Для таких случаев было введено понятие многозначной зависимости.
  
 
== Многозначная зависимость ==
 
== Многозначная зависимость ==
Строка 26: Строка 31:
 
<tex>X \twoheadrightarrow Y</tex> <tex>(X</tex> многозначно определяет <tex>Y)</tex> в отношении <tex>R:</tex>
 
<tex>X \twoheadrightarrow Y</tex> <tex>(X</tex> многозначно определяет <tex>Y)</tex> в отношении <tex>R:</tex>
 
* <tex>X</tex> и <tex>Y - </tex>  множества атрибутов
 
* <tex>X</tex> и <tex>Y - </tex>  множества атрибутов
* Множество значений <tex>Y</tex> не зависит от <tex>R \setminus X \setminus 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>
 
* <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>
 
}}
 
}}
Строка 33: Строка 38:
 
|statement=
 
|statement=
 
Любая [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональная зависимость]] является множественной зависимостью.
 
Любая [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональная зависимость]] является множественной зависимостью.
 +
|proof=
 +
У $Y$ при фиксированном $X$ есть ровно одно значение. То есть мощность множества, которое зависит, равна одному.
 
}}
 
}}
  
 
=== Теорема Фейгина ===
 
=== Теорема Фейгина ===
 
{{Теорема
 
{{Теорема
|statement= Обобщение [[Цели_и_средства_нормализации|теоремы Хита]]: <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y </tex>
+
|statement=Декомпозиция является корректной тогда и только тогда, когда есть соответствующая множественная зависимость: <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y </tex>
 
|proof=
 
|proof=
 
* <tex>\Rightarrow</tex>
 
* <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>R(XYZ)=\pi_{XY}(R) \bowtie \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>(x,y,z) \in R</tex>.
 +
**Мы знаем, что его проекции принадлежат проекциям исходного отношения:  <tex>(x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)</tex>.
 +
**<tex>(x,y,z) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)</tex>.
 +
**Возьмем произвольное дополнительное $z1$, которое было из проекции на $xz$, и произвольное $z2$ из той же проекции:<tex>(x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R)</tex>.
 +
 
 +
Тогда если <tex>(x,y,z1) \in R</tex>, то <tex>(x,y) \in \pi_{XY}(R)</tex>. Если у нас есть <tex>(x, z2)</tex> и кортеж <tex>(x, y)</tex>, то при их соединении мы получим кортеж <tex>(x,y,z2)</tex>, который будет принадлежать естественному соединению.
 +
 
 +
Так как декомпозиция корректна, то <tex>(x,y,z2)\in R</tex>.
 +
 
 +
Итого от выбора конкретных $z1$ и $z2$  у нас наличие или отсутствие $y$ зависеть не может, все будет всегда одинаково.
 
* <tex>\Leftarrow</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>\forall(x,y,z) \in \pi_{XY}(R) \bowtie \pi_{XZ}(R)</tex>. Он был получен из двух половинок: <tex>(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,z) \in \pi_{XY}(R)</tex>), то должно было существовать какой-то $y'$, такой, что $(x,y',z) \in R$. С другой стороны, для того, чтобы существовала первая половинка, должен был существовать какой-то $z'$, такой, что $(x,y,z') \in R$.
** Так как <tex>X \twoheadrightarrow Y, то (x,y,z) \in R \wedge (x,y',z') \in R </tex>
+
** По определению множественной зависимости если $(x,y',z) \in R$, $(x,y,z) \in R$ и $(x,y,z') \in R$, то у нас принадлежат все возможные варианты. Соответственно, <tex>(x,y,z) \in R \wedge (x,y',z') \in R </tex>
 
}}
 
}}
 +
 +
'''Примечание.'''  Теорема является обобщением [[Цели_и_средства_нормализации|теоремы Хита]].
 +
 +
В отличие от теоремы Хита, где доказывалась только достаточность, в теореме Фейгина доказывается необходимость и достаточность.
  
 
=== Теорема о дополнении ===
 
=== Теорема о дополнении ===
Строка 52: Строка 72:
 
|statement=<tex>R(XYZ)</tex> и <tex>X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z</tex>
 
|statement=<tex>R(XYZ)</tex> и <tex>X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z</tex>
 
|proof=
 
|proof=
 +
В доказательстве теоремы Фейгина <tex>Y</tex> и <tex>Z</tex> равноправны.
 +
 +
 
Из <tex>X \twoheadrightarrow Y</tex> по теореме Фейгина следует <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).</tex>
 
Из <tex>X \twoheadrightarrow Y</tex> по теореме Фейгина следует <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).</tex>
  
Строка 57: Строка 80:
 
Применяя еще раз теорему Фейгина, получаем, что <tex>X \twoheadrightarrow Z.</tex>
 
Применяя еще раз теорему Фейгина, получаем, что <tex>X \twoheadrightarrow Z.</tex>
 
}}
 
}}
 
 
 
<tex>X \twoheadrightarrow Y {|} Z</tex> обозначается: <tex>X</tex> множественно определяет <tex>Y</tex> и <tex>Z</tex>.
 
<tex>X \twoheadrightarrow Y {|} Z</tex> обозначается: <tex>X</tex> множественно определяет <tex>Y</tex> и <tex>Z</tex>.
 +
{{Утверждение
 +
|statement=
 +
<tex>\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset</tex>
 +
|proof=
 +
Докажем от противного. Попробуем доказать, что данное утверждение неверно.
  
'''Следствие.''' <tex>\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset</tex>  
+
По определению: для того, чтобы доказать, что множественная зависимость отсутствует, необходимо взять <tex>x</tex>, найти к нему два различных <tex>z</tex> таких, что множества <tex>Y</tex> будут разные. Однако два различных <tex>z</tex> в пустом множестве мы найти не можем.
  
 +
Итого, если одно из множеств пусто, то такая соответствующая множественная зависимость тривиальна и выполняется для всех отношений.
 +
}}
 +
{{Определение
 +
|definition=
 
<tex>X \twoheadrightarrow Y{|}\emptyset</tex> называется тривиальной множественной зависимостью.
 
<tex>X \twoheadrightarrow Y{|}\emptyset</tex> называется тривиальной множественной зависимостью.
 +
}}
  
 
== Четвертая нормальная форма ==
 
== Четвертая нормальная форма ==
Строка 80: Строка 111:
 
|statement=Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
 
|statement=Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
 
|proof=
 
|proof=
* Пока есть множественная зависимость, декомпозируем на два отношения.
+
* Пока есть множественная зависимость, декомпозируем на два отношения (По теореме Фейгина).
 
* Количество атрибутов в каждом отношении всегда уменьшается.
 
* Количество атрибутов в каждом отношении всегда уменьшается.
* в конце останутся либо отношения из одного атрибута, которое находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению
+
* В конце останутся либо отношения из одного атрибута, которые находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению.
 
}}
 
}}
  
=== Приведение к 4НФ ===
+
=== Пример приведения к 4НФ ===
  
 
Пусть задано отношение:
 
Пусть задано отношение:
Строка 126: Строка 157:
 
| Мат.Ан. || Фихтенгольц
 
| Мат.Ан. || Фихтенгольц
 
|}
 
|}
 +
 +
Теорема Фейгина гарантирует, что соответствующая декомпозиция будет корректной.
 +
 +
[[Категория: Базы данных]]

Текущая версия на 19:34, 4 сентября 2022

Мотивация. Аномалии в НФБК

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

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)[/math].
    • Рассмотрим произвольный кортеж из исходного отношения [math](x,y,z) \in R[/math].
    • Мы знаем, что его проекции принадлежат проекциям исходного отношения: [math](x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)[/math].
    • [math](x,y,z) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)[/math].
    • Возьмем произвольное дополнительное $z1$, которое было из проекции на $xz$, и произвольное $z2$ из той же проекции:[math](x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R)[/math].

Тогда если [math](x,y,z1) \in R[/math], то [math](x,y) \in \pi_{XY}(R)[/math]. Если у нас есть [math](x, z2)[/math] и кортеж [math](x, y)[/math], то при их соединении мы получим кортеж [math](x,y,z2)[/math], который будет принадлежать естественному соединению.

Так как декомпозиция корректна, то [math](x,y,z2)\in R[/math].

Итого от выбора конкретных $z1$ и $z2$ у нас наличие или отсутствие $y$ зависеть не может, все будет всегда одинаково.

  • [math]\Leftarrow[/math]
    • Возьмем любой кортеж из естественного соединения: [math]\forall(x,y,z) \in \pi_{XY}(R) \bowtie \pi_{XZ}(R)[/math]. Он был получен из двух половинок: [math](x,y) \in \pi_{XY}(R)\wedge(x,z) \in \pi_{XY}(R)[/math]
    • Чтобы получилась вторая половинка ([math](x,z) \in \pi_{XY}(R)[/math]), то должно было существовать какой-то $y'$, такой, что $(x,y',z) \in R$. С другой стороны, для того, чтобы существовала первая половинка, должен был существовать какой-то $z'$, такой, что $(x,y,z') \in R$.
    • По определению множественной зависимости если $(x,y',z) \in R$, $(x,y,z) \in R$ и $(x,y,z') \in R$, то у нас принадлежат все возможные варианты. Соответственно, [math](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]Y[/math] и [math]Z[/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
СУБД Дейт
СУБД Ульман
Мат.Ан. Фихтенгольц
Мат.Ан. Фихтенгольц

Теорема Фейгина гарантирует, что соответствующая декомпозиция будет корректной.