Функциональные зависимости: замыкание, эквивалентность и правила вывода — различия между версиями
Darkey (обсуждение | вклад) (→Эквивалентность множеств функциональных зависимостей) |
Darkey (обсуждение | вклад) (→Замыкание множества функциональных зависимостей) |
||
Строка 16: | Строка 16: | ||
'''for''' f in closure: | '''for''' f in closure: | ||
'''for''' rule in rules: //rules - правила вывода | '''for''' rule in rules: //rules - правила вывода | ||
− | new_f = rule.apply(f) | + | new_f = rule.apply(f, closure) |
changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе | changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе | ||
'''return''' closure | '''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> | ||
== Эквивалентность множеств функциональных зависимостей == | == Эквивалентность множеств функциональных зависимостей == |
Версия 00:25, 29 декабря 2020
Содержание
Функциональные зависимости
Определение и примеры
Правила вывода функциональных зависимостей
Замыкание множества функциональных зависимостей
Определение: |
Замыкание множества функциональных зависимостей | - множество всех функциональных зависимостей, обозначаемое , которые следуют из заданного множества функциональных зависимостей .
Построение
Set<E> buildClosure(s: Set<E>): closure = Set<E>(s.addAll()) changed = true while (changed): changed = false 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 атрибутов для левой части ФЗ -
. Известно, что . Значит количество тривиальных ФЗЭквивалентность множеств функциональных зависимостей
Здесь и далее
- множества функциональных зависимостей.Определение: |
Определение: |
Задача минимизации ФЗ
Постановка задачи
Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ
такое, что замыкание и совпадают и множество имеет меньшую мощность, чем . Это позволит снизить нагрузку на базу данных.