Функциональные зависимости: замыкание, эквивалентность и правила вывода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оценка мощности замыкания)
(Замыкание множества функциональных зависимостей)
Строка 21: Строка 21:
 
           changed = closure.add(new_f)    //add - возвращает true, если элемент был добавлен, false - иначе
 
           changed = closure.add(new_f)    //add - возвращает true, если элемент был добавлен, false - иначе
 
   '''return''' closure
 
   '''return''' closure
 
=== Оценка мощности замыкания ===
 
Для начала оценим количество тривиальных ФЗ на <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> - базовые нетривиальные зависимости.
 
 
На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.
 
  
 
== Эквивалентность множеств функциональных зависимостей ==
 
== Эквивалентность множеств функциональных зависимостей ==

Версия 20:40, 8 января 2021

Функциональные зависимости

Определение и примеры

Правила вывода функциональных зависимостей

Замыкание множества функциональных зависимостей

Определение:
Замыкание множества функциональных зависимостей [math]S[/math] - множество всех функциональных зависимостей, обозначаемое [math]S^+[/math], которые следуют из заданного множества функциональных зависимостей [math]S[/math].

Построение

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

Эквивалентность множеств функциональных зависимостей

Здесь и далее [math]S, P[/math] - множества функциональных зависимостей.

Определение:
[math]S[/math] слабее [math]P[/math] ([math]P[/math] накрывает [math]S[/math]) тогда и только тогда, когда [math]S^+[/math] является подмножеством [math]P^+[/math]:
[math]S \sqsubset P \Leftrightarrow S^+ \subset P^+[/math]


Определение:
[math]S[/math] эквивалентно [math]P[/math]:
[math]S \equiv P \, \Leftrightarrow \, S \sqsubset P \; \textrm{and} \; P \sqsubset S \, \Leftrightarrow \, S^+ = P^+ [/math]


Задача минимизации ФЗ

Постановка задачи

Найти минимальное множество ФЗ эквивалентное заданному. То есть необходимо найти множество ФЗ [math]P[/math] такое, что замыкание [math]S[/math] и [math]P[/math] совпадают и множество [math]P[/math] имеет меньшую мощность, чем [math]S[/math]. Это позволит снизить нагрузку на базу данных. Но такой подход к решению задачи не применим на практике из-за большой мощности замыкания.