75
правок
Изменения
→Замыкание атрибутов
== Замыкание атрибутов ==
{{Определение |definition=
Замыкание множества атрибутов <tex>X</tex> над множеством ФЗ <tex>S</tex> - максимальное по включению множество атрибутов <tex>X^+_S</tex> функционально зависящих от <tex>S</tex>.
}}
{{Теорема
|id=proposalfirstcorrect
|statement=<tex>A \to B \in S^+ \Leftrigtharrow Leftrightarrow B \subset A^+_S</tex>
|proof= По определению замыкания атрибутов.
}}
Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ: <br/>
Даны множества <tex>S</tex> и <tex>P</tex> и пусть для простоты <tex>P \subset S</tex>, необходимо проверить является ли <tex>P</tex> эквивалентным <tex>S</tex>. Для этого достаточно построить замыкание <tex>P^+_S</tex> и по теореме проверить все фз из <tex>S</tex>, которые отсутствуют в <tex>P</tex>. Если доказать, что из <tex>P</tex> выводимы все базовые правила <tex>S</tex>, то их замыкания ФЗ будут совпадать, следовательно, два множества эквивалентны. Например, пусть <tex>A \to B \in S, A \to B \not\in P </tex>, тогда если <tex>B \in P_S^+</tex>, то<tex> A \to B \in P^+</tex>. {{Следствие|id=proposalfirstcorrect |statement=<tex>X</tex>- надключ <tex> \Leftrightarrow X^+ </tex> - множество всех атрибутов|proof= По определению замыкания атрибутов.}} Данное следствие позволяет формально выделять ключи и надключи.
=== Построение ===
<tex>A \subset X_S^* => X \to A</tex>(по правилу расщепления, т.к. <tex>X_S^*</tex> изначально содержит в себе <tex>X</tex>) <tex>=> X \to B </tex>, то есть <tex>B</tex> входит в замыкание. </br>
2) <tex>X_S^+ \subset X_S^* </tex> <br/>
Доказательство от обратного: Пусть <tex>X_S^+ \not\subset X_S^* => \exists A: A \in X_S^+ \text{ and } A \not\in X_S^*.\; A \in X_S^+ => X \to A =></tex> есть вывод <tex> X->\to X_1^+, ..., X_n^+ \to A </tex> TODO. В этой цепочке найдём первую свежую ФЗ, то есть она не была в базовых ФЗ <tex>X</tex>. Такая фз точно есть в этой цепочке, например, <tex>X_n^+ \to A</tex>, т.к. <tex>A \in X_S^+ \text{ and } A \not\in X_S^* => </tex> такое правило не могло быть в <tex>X</tex>.
}}
