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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность множеств функциональных зависимостей)
(Эквивалентность множеств функциональных зависимостей)
Строка 21: Строка 21:
  
 
== Эквивалентность множеств функциональных зависимостей ==
 
== Эквивалентность множеств функциональных зависимостей ==
 +
Здесь и далее <tex>S, P</tex> - множества функциональных зависимостей.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Множество ФЗ <tex>S</tex> слабее множества ФЗ <tex>P</tex> (<tex>P</tex> накрывает <tex>S</tex>) тогда и только тогда, когда <tex>S^+</tex> является подмножеством <tex>P^+</tex>: <tex>S \sqsubset P \Leftrightarrow S^+ \subset P^+</tex>
+
<tex>S</tex> '''слабее''' <tex>P</tex> (<tex>P</tex> накрывает <tex>S</tex>) тогда и только тогда, когда <tex>S^+</tex> является подмножеством <tex>P^+</tex>: <tex>S \sqsubset P \Leftrightarrow S^+ \subset P^+</tex>
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
<tex>S</tex> '''эквивалентно''' <tex>P</tex> (<tex>P</tex> накрывает <tex>S</tex>): <tex>S \equiv P \Leftrightarrow S \sqsubset P \& P \sqsubset S \Leftrigtharrow S^+ = P^+ </tex>
 
}}
 
}}

Версия 23:17, 28 декабря 2020

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

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

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

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

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

Построение

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)
         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]P[/math] накрывает [math]S[/math]): [math]S \equiv P \Leftrightarrow S \sqsubset P \& P \sqsubset S \Leftrigtharrow S^+ = P^+ [/math]