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

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

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

Замыкание множества атрибутов [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 \subset S[/math], необходимо проверить является ли [math]P[/math] эквивалентным [math]S[/math]. Для этого достаточно построить замыкание [math]P^+_S[/math] и по теореме проверить все фз из [math]S[/math], которые отсутствуют в [math]P[/math]. Если доказать, что из [math]P[/math] выводимы все базовые правила [math]S[/math], то их замыкания ФЗ будут совпадать, следовательно, два множества эквивалентны. Например, пусть [math]A \to B \in S, A \to B \not\in P [/math], тогда если [math]B \in P_S^+[/math], то [math] A \to B \in 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]. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, т.к. все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ.

Выводы о НМФЗ

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