Функциональные зависимости: замыкание, эквивалентность и правила вывода — различия между версиями
Darkey (обсуждение | вклад) (→Оценка мощности замыкания) |
Darkey (обсуждение | вклад) (→Постановка задачи) |
||
Строка 40: | Строка 40: | ||
=== Задача минимизации ФЗ === | === Задача минимизации ФЗ === | ||
==== Постановка задачи ==== | ==== Постановка задачи ==== | ||
− | Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ <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>. Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания. |
Версия 00:46, 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
Оценка мощности замыкания
Для начала оценим количество тривиальных ФЗ на
атрибутах. Количество способов выбрать атрибутов из для левой части ФЗ - , количество способов выбрать непустое подмножество из левой части - . Известно, что . Значит количество тривиальных ФЗ: . Заметим, что при построении замыкания нельзя не учитывать тривиальные зависимости, так как при применении правил вывода, правила композиции, например, к нетривиальной и тривиальной зависимостям можно получить в итоге нетривиальную зависимость. Получается, что мощность не меньше, чем , где - базовые нетривиальные зависимости.На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.
Эквивалентность множеств функциональных зависимостей
Здесь и далее
- множества функциональных зависимостей.Определение: |
Определение: |
Задача минимизации ФЗ
Постановка задачи
Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ
такое, что замыкание и совпадают и множество имеет меньшую мощность, чем . Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания.