Материал из Викиконспекты
Замыкание атрибутов
{{|definition=
Замыкание множества атрибутов [math]X[/math] над множеством ФЗ [math]S[/math] - максимальное по включению множество атрибутов [math]X^+_S[/math] функционально зависящих от [math]S[/math].
}}
Максимальный размер [math]X^+_S[/math] равен числу атрибутов в отношении.
Основное свойство замыкания множества атрибутов
| Теорема: |
[math]A \to B \in S^+ \Leftrigtharrow B \subset A^+_S[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
По определению замыкания атрибутов. |
| [math]\triangleleft[/math] |
Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ:
Даны множества [math]S[/math] и [math]P[/math] и пусть для простоты [math]P \subset S[/math], необходимо проверить является ли [math]P[/math] эквивалентным [math]S[/math]. Для этого достаточно построить замыкание [math]P^+_S[/math] и по теореме проверить все фз из [math]S[/math], которые отсутствуют в [math]P[/math]. Если доказать, что из [math]P[/math] выводимы все базовые правила [math]S[/math], то их замыкания ФЗ будут совпадать, следовательно, два множества эквивалентны. Например, пусть [math]A \to B \in S, A \to B \not\in P [/math], тогда если [math]B \in P_S^+[/math], то[math] A \to B \in P^+\lt tex\gt .
=== Построение ===
\lt tex\gt X_S^*[/math] = X
do
foreach [math]A \gets B \in S[/math]:
if [math]A \subset X_S^*[/math] then [math] X_S^* = X_S^* \cup B[/math]
while есть изменения
| Теорема: |
[math]X^+_S = X^*_S[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
1) [math]X_S^+ \supset X_S^* [/math]
[math]A \subset X_S^* =\gt X \to A[/math](по правилу расщепления, т.к. [math]X_S^*[/math] изначально содержит в себе [math]X[/math]) [math]=\gt X \to B [/math], то есть [math]B[/math] входит в замыкание. </br>
2) [math]X_S^+ \subset X_S^* [/math]
Доказательство от обратного: Пусть [math]X_S^+ \not\subset X_S^* =\gt \exists A: A \in X_S^+ \text{ and } A \not\in X_S^*.\; A \in X_S^+ =\gt X \to A =\gt [/math] есть вывод [math] X-\gt X_1^+, ..., X_n^+ \to A [/math] TODO |
| [math]\triangleleft[/math] |
