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

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

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

Замыкание множества атрибутов [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^*[/math] = X
do
   foreach [math]A \gets B \in 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]

Доказательство по построению: По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, т.к. старая ФЗ может быть получена по правилу объединения. Для левой части каждого правила пытаемся удалить по одному атрибуту [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]. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, т.к. все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ.

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

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