75
правок
Изменения
→Построение замыкания атрибутов
{{Определение
|definition=
Замыкание множества атрибутов <tex>X</tex> над множеством ФЗ <tex>S</tex> {{- --}} максимальное по включению множество атрибутов , обозначаемое <tex>X^+_S</tex> , функционально зависящих от <tex>S</tex>.
}}
Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ: <br/>
Даны множества функциональных зависимостей <tex>S</tex> и <tex>P</tex> и пусть для простоты <tex>P \subset S</tex>, необходимо проверить является ли <tex>P</tex> эквивалентным <tex>S</tex>. Для этого достаточно построить замыкание , то есть требуется показать, что <tex>S^+ \subset P^+_S</tex> и по теореме проверить все фз из <tex>P^+ \subset S^+</tex>. Теорема выше позволяет проверять принадлежит ли ФЗ некоторому замыканию функциональных зависимостей, тогда чтобы показать, которые отсутствуют в что <tex>S^+ \subset P^+</tex>. Если доказатьдостаточно проверить, что из <tex>P\forall A \to B \in S</tex> выводимы все базовые правила выполняется <tex>SA \to B \subset P^+</tex>, то их замыкания ФЗ будут совпадать, следовательно, два множества эквивалентны. Например, пусть есть для каждой базовой функциональной зависимости <tex>A \to B \in </tex> из <tex>S, A \to B \not\in P </tex>, тогда если построить <tex>B \in P_SA^+_P</tex> замыкание атрибутов над <tex>P</tex>и проверить, то что <tex> A \to B \in Psubset A^+_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^*= X</tex> = X \\<tex>X_S^*</tex> исходно совпадает с множеством, замыкание атрибутов которого ищем
'''do'''
'''foreach''' <tex>A \gets to B \in S</tex>: \\<tex>S</tex> {{---}} множество ФЗ
'''if''' <tex>A \subset X_S^*</tex> then <tex> X_S^* = X_S^* \cup B</tex>
'''while''' есть изменения
|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> '''минимально по вклюючениювключению''', если ни одна функциональная зависимость из множества <tex>S</tex> не может быть удалена из
множества <tex>S</tex> без изменения его замыкания <tex>S^+</tex>.
}}
|statement=Для любого множества ФЗ существует эквивалентное неприводимое множество ФЗ (НМФЗ).
|proof= Доказательство по построению: <br>
* По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, т.к. так как старая ФЗ может быть получена по правилу объединения. * Для левой части каждого правила пытаемся минимизировать по включению левую часть всеми возможными способами. Чтобы проверить, что атрибут X можно удалить по одному атрибуту из <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>. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, т.к. так как все операции по приведению множества к неприводимому сохраняют исходное замыканиче замыкание ФЗ. === Выводы Замечания о НМФЗ ===
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
* Неприводимое множество ФЗ может не являться минимальным по мощности.
