75
правок
Изменения
→Замыкание множества функциональных зависимостей
'''for''' f in closure:
'''for''' rule in rules: //rules - правила вывода
new_f = rule.apply(f, closure)
changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе
'''return''' closure
=== Оценка мощности замыкания ===
Для начала оценим количество функциональных тривиальных зависимостей на n атрибутах. Количество способов выбрать k атрибутов для левой части ФЗ - <tex>{\binom {n}{k}}<\tex>, количество способов выбрать непустое подмножество из левой части - <tex>2^k - 1</tex>. Известно, что <tex>\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}</tex>. Значит количество тривиальных ФЗ <tex>\sum _{k=0}^{n}{\binom {n}{k}}(2^{k} - 1)=O((3)^{n})</tex>
== Эквивалентность множеств функциональных зависимостей ==
