Функциональные зависимости: замыкание, эквивалентность и правила вывода — различия между версиями
Darkey (обсуждение | вклад) (→Построение) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 7: | Строка 7: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Замыкание множества функциональных зависимостей <tex>S</tex> - множество всех функциональных зависимостей, обозначаемое <tex>S^+</tex>, которые следуют из заданного множества функциональных зависимостей <tex>S</tex>. | + | Замыкание множества функциональных зависимостей <tex>S</tex> {{---}} множество всех функциональных зависимостей, обозначаемое <tex>S^+</tex>, которые следуют из заданного множества функциональных зависимостей <tex>S</tex>. |
}} | }} | ||
=== Построение === | === Построение === | ||
Строка 21: | Строка 21: | ||
changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе | changed = closure.add(new_f) //add - возвращает true, если элемент был добавлен, false - иначе | ||
'''return''' closure | '''return''' closure | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Эквивалентность множеств функциональных зависимостей == | == Эквивалентность множеств функциональных зависимостей == | ||
− | Здесь и далее <tex>S, P</tex> - множества функциональных зависимостей. | + | Здесь и далее <tex>S, P</tex> {{---}} множества функциональных зависимостей. |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
Строка 39: | Строка 33: | ||
<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>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>. Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания. | Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ <tex>P</tex> такое, что замыкание <tex>S</tex> и <tex>P</tex> совпадают и множество <tex>P</tex> имеет меньшую мощность, чем <tex>S</tex>. Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания. |
Текущая версия на 19:13, 4 сентября 2022
Содержание
Функциональные зависимости
Определение и примеры
Правила вывода функциональных зависимостей
Замыкание множества функциональных зависимостей
Определение: |
Замыкание множества функциональных зависимостей | — множество всех функциональных зависимостей, обозначаемое , которые следуют из заданного множества функциональных зависимостей .
Построение
Set<E> buildClosure(s: Set<E>): closure = Set<E>(s) 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
Эквивалентность множеств функциональных зависимостей
Здесь и далее
— множества функциональных зависимостей.Определение: |
Определение: |
Оценка мощности замыкания
Для начала оценим количество тривиальных ФЗ на
атрибутах. Количество способов выбрать атрибутов из для левой части ФЗ — , количество способов выбрать непустое подмножество из левой части для правой — . Известно, что . Значит количество тривиальных ФЗ: . Заметим, что при построении замыкания нельзя не учитывать тривиальные зависимости, так как при применении правил вывода, правила композиции, например, к нетривиальной и тривиальной зависимостям можно получить в итоге нетривиальную зависимость. Получается, что мощность порядка , где — количество базовых нетривиальных зависимостей.На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.
Задача минимизации ФЗ
Постановка задачи
Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ
такое, что замыкание и совпадают и множество имеет меньшую мощность, чем . Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания.