1632
правки
Изменения
м
=== Определение и примеры ====== Правила вывода функциональных зависимостей ===
=== Оценка мощности замыкания ===
Для начала оценим количество тривиальных ФЗ на <tex>n</tex> атрибутах. Количество способов выбрать <tex>k</tex> атрибутов из <tex>n</tex> для левой части ФЗ - <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>.
Заметим, что при построении замыкания нельзя не учитывать тривиальные зависимости, так как при применении правил вывода, правила композиции, например, к нетривиальной и тривиальной зависимостям можно получить в итоге нетривиальную зависимость. Получается, что мощность не меньше, чем <tex>O(m * 3^n)</tex>, где <tex>m</tex> - базовые нетривиальные зависимости.
На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.
rollbackEdits.php mass rollback
== Функциональные зависимости ==
== Замыкание множества функциональных зависимостей ==
{{Определение
|definition=
Замыкание множества функциональных зависимостей <tex>S</tex> {{- --}} множество всех функциональных зависимостей, обозначаемое <tex>S^+</tex>, которые следуют из заданного множества функциональных зависимостей <tex>S</tex>.
}}
=== Построение ===
Set<E> '''buildClosure'''(s: Set<E>):
closure = Set<E>(s.addAll())
changed = true
'''while''' (changed):
changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе
'''return''' closure
== Эквивалентность множеств функциональных зависимостей ==
Здесь и далее <tex>S, P</tex> {{- --}} множества функциональных зависимостей.
{{Определение
|definition =
<tex>S</tex> '''эквивалентно''' <tex>P</tex>: <br/><tex>S \equiv P \, \Leftrightarrow \, S \sqsubset P \; \textrm{and} \; P \sqsubset S \, \Leftrightarrow \, S^+ = P^+ </tex>
}}
=== Оценка мощности замыкания ===
Для начала оценим количество тривиальных ФЗ на <tex>n</tex> атрибутах. Количество способов выбрать <tex>k</tex> атрибутов из <tex>n</tex> для левой части ФЗ {{---}} <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>.
Заметим, что при построении замыкания нельзя не учитывать тривиальные зависимости, так как при применении правил вывода, правила композиции, например, к нетривиальной и тривиальной зависимостям можно получить в итоге нетривиальную зависимость. Получается, что мощность порядка <tex>O(m3^n)</tex>, где <tex>m</tex> {{---}} количество базовых нетривиальных зависимостей.
На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.
=== Задача минимизации ФЗ ===
==== Постановка задачи ====
Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ <tex>P</tex> такое, что замыкание <tex>S</tex> и <tex>P</tex> совпадают и множество <tex>P</tex> имеет меньшую мощность, чем <tex>S</tex>. Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания.
