Функциональные зависимости: замыкание атрибутов, неприводимые множества функциональных зависимостей, их построение

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Замыкание атрибутов

Определение:

Замыкание множества атрибутов [math]X[/math] над множеством ФЗ [math]S[/math] — максимальное по включению множество атрибутов, обозначаемое [math]X^+_S[/math], функционально зависящих от [math]S[/math].

Максимальный размер [math]X^+_S[/math] равен числу атрибутов в отношении.

Основное свойство замыкания множества атрибутов

Теорема:

[math]A \to B \in S^+ \Leftrightarrow B \subset A^+_S[/math]

Доказательство:

[math]\triangleright[/math]

По определению замыкания атрибутов.

[math]\triangleleft[/math]

Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ:
Даны множества функциональных зависимостей [math]S[/math] и [math]P[/math], необходимо проверить является ли [math]P[/math] эквивалентным [math]S[/math], то есть требуется показать, что [math]S^+ \subset P^+[/math] и [math]P^+ \subset S^+[/math]. Теорема выше позволяет проверять принадлежит ли ФЗ некоторому замыканию функциональных зависимостей, тогда чтобы показать, что [math]S^+ \subset P^+[/math] достаточно проверить, что [math]\forall A \to B \in S[/math] выполняется [math]A \to B \subset P^+[/math], то есть для каждой базовой функциональной зависимости [math]A \to B[/math] из [math]S[/math] построить [math]A^+_P[/math] замыкание атрибутов над [math]P[/math] и проверить, что [math]B \subset A^+_P[/math].

Утверждение:

Следствие: [math]X[/math] — надключ [math] \Leftrightarrow X^+ [/math] — множество всех атрибутов

[math]\triangleright[/math]

[math](=\gt )[/math] По определению замыкания атрибутов, так как все атрибуты функционально зависят от [math]X[/math]. [math](\lt =)[/math] [math]X^+[/math] — множество всех атрибутов и по теореме [math]\exists \; X \to X^+[/math], то по определению функциональной зависимости [math]X[/math] соответствует ровно один [math]X^+[/math] и значит [math]X[/math] — надключ.

[math]\triangleleft[/math]

Данное следствие позволяет формально выделять ключи и надключи.

Построение замыкания атрибутов

[math]X_S^* = X[/math]        \\[math]X_S^*[/math] исходно совпадает с множеством, замыкание атрибутов которого ищем
do
   foreach [math]A \to B \in S[/math]:      \\[math]S[/math] — множество ФЗ
      if [math]A \subset X_S^*[/math] then [math] X_S^* =  X_S^* \cup B[/math]
while есть изменения

Теорема:

[math]X^+_S = X^*_S[/math]

Доказательство:

[math]\triangleright[/math]

1) [math]X_S^+ \supset X_S^* [/math] [math]A \subset X_S^* =\gt X \to A[/math](по правилу расщепления, так как [math]X_S^*[/math] изначально содержит в себе [math]X[/math]) [math]=\gt X \to B [/math], то есть [math]B[/math] входит в замыкание. 2) [math]X_S^+ \subset X_S^* [/math] Доказательство от обратного: Пусть [math]X_S^+ \not\subset X_S^* =\gt \exists A: A \in X_S^+ \text{ and } A \not\in X_S^*.\; A \in X_S^+ =\gt X \to A =\gt [/math] есть вывод [math] X \to X_1^+, ..., X_n^+ \to A[/math]. В этой цепочке найдём первую свежую ФЗ, то есть она не была в базовых ФЗ [math]X[/math]. Такая функциональная зависимость точно есть в этой цепочке, например, [math]X_n^+ \to A[/math], так как [math]A \in X_S^+ \text{ and } A \not\in X_S^* =\gt [/math] такое правило не могло быть в [math]X[/math]. Получается, что атрибут A не был добавлен в [math]X^*_S[/math] в алгоритме, такое может быть только если атрибут A уже содержался в [math]X =\gt [/math] противоречие.

[math]\triangleleft[/math]

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

Определение:

Множество ФЗ [math]S[/math] неприводимо, если: Каждая правая часть ФЗ содержит ровно один атрибут Каждая левая часть ФЗ минимальна по включению [math]S[/math] минимально по включению

Определение:

Множество ФЗ [math]S[/math] минимально по включению, если ни одна функциональная зависимость из множества [math]S[/math] не может быть удалена из множества [math]S[/math] без изменения его замыкания [math]S^+[/math].

Теорема:

Для любого множества ФЗ существует эквивалентное неприводимое множество ФЗ (НМФЗ).

Доказательство:

[math]\triangleright[/math]

Доказательство по построению: По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, так как старая ФЗ может быть получена по правилу объединения. Для каждого правила пытаемся минимизировать по включению левую часть всеми возможными способами. Чтобы проверить, что атрибут X можно удалить из [math]A \cup \{X\} \to B[/math], нужно проверить, что если [math]B \subset A^+_S[/math] выполняется, то [math]A \to B[/math], то можно минимизировать левую часть, отбросив [math]X[/math]. Потенциально из одной ФЗ может получиться множество ФЗ, где левая часть минимальна по включению. Пытаемся удалить по одному правилу [math]A \to B[/math]. Если [math]B \subset A^+_{S\backslash\{A \to B\}} \to B[/math], то по теореме [math]A \to B \in S^+[/math], значит это правило можно удалить.

[math]\triangleleft[/math]

Оценка времени построения НМФЗ

• Расщепление правых частей - линейно по размеру правых частей.
• Удаление атрибута [math]A \cup \{X\} \to B[/math]. На данном этапе из одной ФЗ возможно получить множество ФЗ минимальных по включению. Синтетическая оценка множества потенциальных множеств минимальных по включению мощностью [math] {\frac {n}{2}}[/math] это [math]{\binom {n}{{\frac {n}{2}}}} \approx 2^n [/math]. То есть на ФЗ с большой левой частью возможен экспоненциальный рост количества ФЗ с минимальной по включению левой частью. Но на реальных данных большая левая часть в ФЗ практически не встречается.
• Удаление правила [math]A \to B[/math]. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, так как все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ.

Замечания о НМФЗ

• Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
• Неприводимое множество ФЗ может не являться минимальным по мощности.