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