Просмотр исходного текста страницы Функциональные зависимости: замыкание атрибутов, неприводимые множества функциональных зависимостей, их построение

== Замыкание атрибутов ==
{{Определение 
|definition=
Замыкание множества атрибутов <tex>X</tex> над множеством ФЗ <tex>S - </tex>  максимальное по включению множество атрибутов, обозначаемое <tex>X^+_S</tex>, функционально зависящих от <tex>S</tex>.
}}

Максимальный размер <tex>X^+_S</tex> равен числу атрибутов в отношении.

=== Основное свойство замыкания множества атрибутов ===
{{Теорема
|id=proposalfirstcorrect 
|statement=<tex>A \to  B \in S^+ \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>.

{{Утверждение
|statement=
'''Следствие''':<br/><tex>X</tex>- надключ <tex> \Leftrightarrow X^+ </tex> - множество всех атрибутов
|proof=
<tex>(=>)</tex><br>По определению замыкания атрибутов, так как все атрибуты функционально зависят от <tex>X</tex>.<br/>
<tex>(<=)</tex><br><tex>X^+</tex> - множество всех атрибутов и по теореме <tex>\exists \; X \to X^+</tex>, то по определению функциональной зависимости <tex>X</tex> соответствует ровно один <tex>X^+</tex> и значит <tex>X</tex> - надключ.
}}
Данное следствие позволяет формально выделять ключи и надключи.

=== Построение замыкания атрибутов ===

 <tex>X_S^*</tex> = X
 '''do'''
    '''foreach''' <tex>A \gets B \in S</tex>:
       '''if''' <tex>A \subset X_S^*</tex> then <tex> X_S^* =  X_S^* \cup B</tex>
 '''while''' есть изменения

{{Теорема
|id=proposalfirstcorrect 
|statement=<tex>X^+_S = X^*_S</tex>
|proof=
1) <tex>X_S^+ \supset X_S^* </tex> <br>
<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>. В этой цепочке найдём первую свежую ФЗ, то есть она не была в базовых ФЗ <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>. Получается, что атрибут A не был добавлен в <tex>X^*_S</tex> в алгоритме, такое может быть только если атрибут A уже содержался в <tex>X => </tex> противоречие. 
}}

== Неприводимые множества функциональных зависимостей ==
{{Определение 
|definition=
Множество ФЗ <tex>S</tex> '''неприводимо''', если: <br>
* Каждая правая часть ФЗ содержит ровно один атрибут
* Каждая левая часть ФЗ минимальна по включению
* <tex>S</tex> минимально по включению
}}

{{Определение 
|definition=
Множество ФЗ <tex>S</tex> '''минимально по включению''', если ни одна функциональная зависимость из множества <tex>S</tex> не может быть удалена из
множества <tex>S</tex> без изменения его замыкания <tex>S^+</tex>.
}}

{{Теорема
|id=proposalfirstcorrect 
|statement=Для любого множества ФЗ существует эквивалентное неприводимое множество ФЗ (НМФЗ).
|proof= Доказательство по построению: <br>
* По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, т.к. старая ФЗ может быть получена по правилу объединения. 
* Для левой части каждого правила пытаемся удалить по одному атрибуту <tex>A \cup \{X\} \to B</tex>. Если <tex>B \subset A^+_S</tex> выполняется, то <tex>A \to B</tex>, то можно минимизировать левую часть, отбросив <tex>X</tex>.
* Пытаемся удалить по одному правилу <tex>A \to B</tex>. Если <tex>B \subset A^+_{S\backslash\{A \to B\}} \to B</tex> выполняется, то по теореме <tex>A \to B \in S^+</tex>, значит от этого правила можно избавится.
}}

=== Оценка времени построения === 
* Расщепление правых частей - линейно по размеру правых частей.
* Удаление атрибута <tex>A \cup \{X\} \to B</tex>. На данном этапе из одной ФЗ возможно получить множество ФЗ минимальных по включению. Синтетическая оценка множества потенциальных множеств минимальных по включению мощностью <tex> {\frac {n}{2}}</tex> это  <tex>{\binom {n}{{\frac {n}{2}}}} \approx 2^n </tex>. То есть на ФЗ с большой левой частью возможен экспоненциальный рост количества ФЗ с минимальной по включению левой частью. Но на реальных данных большая левая часть в ФЗ практически не встречается. 
* Удаление правила <tex>A \to B</tex>. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, т.к. все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ. 
=== Замечания о НМФЗ ===
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
* Неприводимое множество ФЗ может не являться минимальным по мощности.