75
правок
Изменения
→Построение замыкания атрибутов
<tex>X_S^* = X</tex> \\<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''' есть изменения
|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>, значит это правило можно удалить.
}}
