75
правок
Изменения
→Неприводимые множества функциональных зависимостей
}}
{{Определение
|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\\\{A -> B\} \to B</tex> выполняется, то по теореме <tex>A \to B \in S^+</tex>, значит от этого правила можно избавится.
}}
=== Оценка времени построения ===
* Расщепление правых частей - линейно по размеру правых частей.
* Удаление атрибута <tex>A \cup \{X\} \to B</tex>. На данном этапе из одной ФЗ возможно получить множество ФЗ минимальных по включению. Синтетическая оценка множества потенциальных множеств минимальных по включению мощностью <tex>n/2: {\binom}_{n}{n/2} \approx 2^n</tex>. То есть на ФЗ с большой левой частью возможен экспоненциальный рост количества ФЗ с минимальной по включению левой частью. Но на реальных данных большая левая часть в ФЗ практически не встречается.
* Удаление правила <tex>A \to B</tex>
=== Пример построения ===
* <tex>LId \to DeptHead </tex>
* <tex>Lecturer \; Table \to DeptHead </tex> - т.к.
=== Выводы о НМФЗ ===
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
* Неприводимое множество ФЗ может не являться минимальным
