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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
== Функциональные зависимости ==  
 
== Функциональные зависимости ==  
 
== Определение и примеры ==
 
== Определение и примеры ==

Текущая версия на 19:13, 4 сентября 2022

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

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

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

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

Определение:
Замыкание множества функциональных зависимостей [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]n[/math] атрибутах. Количество способов выбрать [math]k[/math] атрибутов из [math]n[/math] для левой части ФЗ — [math]{\binom {n}{k}}[/math], количество способов выбрать непустое подмножество из левой части для правой — [math]2^k - 1[/math]. Известно, что [math]\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}[/math]. Значит количество тривиальных ФЗ: [math]\sum _{k=0}^{n}{\binom {n}{k}}(2^{k} - 1)=O(3^{n})[/math]. Заметим, что при построении замыкания нельзя не учитывать тривиальные зависимости, так как при применении правил вывода, правила композиции, например, к нетривиальной и тривиальной зависимостям можно получить в итоге нетривиальную зависимость. Получается, что мощность порядка [math]O(m3^n)[/math], где [math]m[/math] — количество базовых нетривиальных зависимостей.

На практике замыкания ФЗ не применимы, так как мощность в реальных приложениях слишком велика.

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

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

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