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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Теорема Фейгина)
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 2 участников)
Строка 31: Строка 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>
 
}}
 
}}
Строка 44: Строка 44:
 
=== Теорема Фейгина ===
 
=== Теорема Фейгина ===
 
{{Теорема
 
{{Теорема
−
|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>
 
}}
 
}}
  
Строка 63: Строка 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>
  

Текущая версия на 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
СУБД Дейт
СУБД Ульман
Мат.Ан. Фихтенгольц
Мат.Ан. Фихтенгольц

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Многозначные_зависимости_и_четвертая_нормальная_форма&oldid=85531»