1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Мотивация. Аномалии в НФБК ==
Рассмотрим следующий пример:
Тогда все атрибуты будут ключевыми: у курса и лектора бывает много книг, лектор может рекомендовать книгу по нескольким курсам, книгу для курса могут рекомендовать все лекторы этого курса.
Поэтому здесь присутствуют только тривиальные функциональные зависимости, поэтому следовательно отношение находится в [[Нормальные_формы:_третья_и_Бойса-Кодда|нормальной форме Бойса-Кодда]].
При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будут все 3 вида аномалии:
* '''Вставки''': невозможно указать литературу по курсу без преподавателя.
* '''Удаления''': нельзя удалить преподавателя, не потеряв литературу по курсу.
<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= Обобщение [[Цели_и_средства_нормализации|теоремы Хита]]Декомпозиция является корректной тогда и только тогда, когда есть соответствующая множественная зависимость: <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)</tex>.**Рассмотрим произвольный кортеж из исходного отношения <tex>(x,y,z) \Rightarrow 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 \Leftrightarrow </tex>, то <tex>(x,y) \in \pi_{XY}(R) \Leftrightarrow </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>\forall(x,y,z) \in \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Rightarrow </tex>. Он был получен из двух половинок: <tex>(x,y) \in \pi_{XY}(R)\wedge(x,z) \in \pi_{XY}(R)</tex>** Тогда Чтобы получилась вторая половинка (<tex>(x,z) \exists in \pi_{XY}(R)</tex>), то должно было существовать какой-то $y'$, такой, что $(x,y',z) \in R$. С другой стороны, для того, чтобы существовала первая половинка, должен был существовать какой-то $z'$, такой, что $(x,y,z':) \in R$.** По определению множественной зависимости если $(x,y',z) \in R$, $(x,y,z) \wedgein R$ и $(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>Y</tex> и <tex>Z</tex> равноправны.
Из <tex>X \twoheadrightarrow Y</tex> по теореме Фейгина следует <tex>R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).</tex>
