1632
правки
Изменения
м
'''СледствиеПо определению: для того, чтобы доказать, что множественная зависимость отсутствует, необходимо взять <tex>x</tex>, найти к нему два различных <tex>z</tex> таких, что множества <tex>Y</tex> будут разные.''' Однако два различных <tex>\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptysetz</tex> в пустом множестве мы найти не можем.
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>
}}
Любая [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функциональная зависимость]] является множественной зависимостью.
|proof=
У $Y$ при фиксированном $X$ есть ровно одно значение. То есть мощность множества, которое зависит, равно равна одному.
}}
=== Теорема Фейгина ===
{{Теорема
|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>
Применяя еще раз теорему Фейгина, получаем, что <tex>X \twoheadrightarrow 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=
Докажем от противного. Попробуем доказать, что данное утверждение неверно.
Итого, если одно из множеств пусто, то такая соответствующая множественная зависимость тривиальна и выполняется для всех отношений.
}}
{{Определение
|definition=
<tex>X \twoheadrightarrow Y{|}\emptyset</tex> называется тривиальной множественной зависимостью.
}}
== Четвертая нормальная форма ==
|statement=Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
|proof=
* Пока есть множественная зависимость, декомпозируем на два отношения(По теореме Фейгина).
* Количество атрибутов в каждом отношении всегда уменьшается.
* в В конце останутся либо отношения из одного атрибута, которые находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению.
}}
| Мат.Ан. || Фихтенгольц
|}
Теорема Фейгина гарантирует, что соответствующая декомпозиция будет корректной.
[[Категория: Базы данных]]
