75
правок
Изменения
→Неприводимые множества функциональных зависимостей
|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>. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, т.к. так как все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ.
=== Замечания о НМФЗ ===
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
* Неприводимое множество ФЗ может не являться минимальным по мощности.
