75
правок
Изменения
→Неприводимые множества функциональных зависимостей
}}
=== aaa ===
{{Теорема
|id=proposalfirstcorrect
* Расщепление правых частей - линейно по размеру правых частей.
* Удаление атрибута <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> === Пример построения ===Дано: <br>* <tex>LId \to Lecturer \; Phone</tex>* <tex>Lecturer \to Phone </tex>* <tex>LId \to DeptHead</tex>* <tex>Lecturer \; Phone \; Table \to DeptHead </tex>Неприводимое множество . На этом этапе не добавляем ФЗ: <br>* <tex>LId \to Lecturer</tex> - расщепили 1-ю , а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ, при на этом <tex>LId \to Phone</tex> не понадобитсяэтапе можно рассматривать лишь один раз, т.к. выводится из <tex>LId \to Lecturer \to Phone</tex>* <tex>Lecturer \to Phone </tex>* <tex>LId \to DeptHead </tex>* <tex>Lecturer \; Table \to DeptHead </tex> - т.все операции по приведению множества кнеприводимому сохраняют исходное замыканиче ФЗ.
=== Выводы о НМФЗ ===
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
* Неприводимое множество ФЗ может не являться минимальным по мощности.
