1632
правки
Изменения
м
rollbackEdits.php mass rollback
<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>
