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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оценка времени построения)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Замыкание множества атрибутов <tex>X</tex> над множеством ФЗ <tex>S</tex> - максимальное по включению множество атрибутов <tex>X^+_S</tex> функционально зависящих от <tex>S</tex>.
+
Замыкание множества атрибутов <tex>X</tex> над множеством ФЗ <tex>S</tex> {{---}} максимальное по включению множество атрибутов, обозначаемое <tex>X^+_S</tex>, функционально зависящих от <tex>S</tex>.
 
}}
 
}}
  
Строка 15: Строка 15:
  
 
Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ: <br/>
 
Данная теорема позволяет проверять эквивалентность множеств ФЗ без вычисления замыканий ФЗ: <br/>
Даны множества <tex>S</tex> и <tex>P</tex> и пусть для простоты <tex>P \subset S</tex>, необходимо проверить является ли <tex>P</tex> эквивалентным <tex>S</tex>. Для этого достаточно построить замыкание <tex>P^+_S</tex> и по теореме проверить все фз из <tex>S</tex>, которые отсутствуют в <tex>P</tex>. Если доказать, что из <tex>P</tex> выводимы все базовые правила <tex>S</tex>, то их замыкания ФЗ будут совпадать, следовательно, два множества эквивалентны. Например, пусть <tex>A \to B \in S, A \to B \not\in P </tex>, тогда если <tex>B \in P_S^+</tex>, то <tex> A \to B \in P^+</tex>.
+
Даны множества функциональных зависимостей <tex>S</tex> и <tex>P</tex>, необходимо проверить является ли <tex>P</tex> эквивалентным <tex>S</tex>, то есть требуется показать, что <tex>S^+ \subset  P^+</tex> и <tex>P^+ \subset S^+</tex>. Теорема выше позволяет проверять принадлежит ли ФЗ некоторому замыканию функциональных зависимостей, тогда чтобы показать, что <tex>S^+ \subset P^+</tex> достаточно проверить, что <tex>\forall A \to B \in S</tex> выполняется <tex>A \to B \subset P^+</tex>, то есть для каждой базовой функциональной зависимости <tex>A \to B</tex> из <tex>S</tex> построить <tex>A^+_P</tex> замыкание атрибутов над <tex>P</tex> и проверить, что <tex>B \subset A^+_P</tex>.
 
 
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
'''Следствие''':<br/><tex>X</tex>- надключ <tex> \Leftrightarrow X^+ </tex> - множество всех атрибутов
+
'''Следствие''':<br/><tex>X</tex> {{---}} надключ <tex> \Leftrightarrow X^+ </tex> {{---}} множество всех атрибутов
 
|proof=
 
|proof=
<tex>(=>)</tex><br>По определению замыкания атрибутов, т.к все атрибуты функционально зависят от X.<br/>
+
<tex>(=>)</tex><br>По определению замыкания атрибутов, так как все атрибуты функционально зависят от <tex>X</tex>.<br/>
<tex>(<=)</tex><br><tex>X^+</tex> - множество всех атрибутов и по теореме <tex>\exists \; X \to X^+</tex>, то по определению функциональной зависимости <tex>X</tex> соответствует ровно один <tex>X^+</tex> и значит <tex>X</tex> - надключ.
+
<tex>(<=)</tex><br><tex>X^+</tex> {{---}} множество всех атрибутов и по теореме <tex>\exists \; X \to X^+</tex>, то по определению функциональной зависимости <tex>X</tex> соответствует ровно один <tex>X^+</tex> и значит <tex>X</tex> {{---}} надключ.
 
}}
 
}}
 
Данное следствие позволяет формально выделять ключи и надключи.
 
Данное следствие позволяет формально выделять ключи и надключи.
  
=== Построение ===
+
=== Построение замыкания атрибутов ===
  
  <tex>X_S^*</tex> = X
+
  <tex>X_S^* = X</tex>       \\<tex>X_S^*</tex> исходно совпадает с множеством, замыкание атрибутов которого ищем
 
  '''do'''
 
  '''do'''
     '''foreach''' <tex>A \gets B \in S</tex>:
+
     '''foreach''' <tex>A \to B \in S</tex>:     \\<tex>S</tex> {{---}} множество ФЗ
 
       '''if''' <tex>A \subset X_S^*</tex> then <tex> X_S^* =  X_S^* \cup B</tex>
 
       '''if''' <tex>A \subset X_S^*</tex> then <tex> X_S^* =  X_S^* \cup B</tex>
 
  '''while''' есть изменения
 
  '''while''' есть изменения
Строка 38: Строка 37:
 
|statement=<tex>X^+_S = X^*_S</tex>
 
|statement=<tex>X^+_S = X^*_S</tex>
 
|proof=
 
|proof=
1) <tex>X_S^+ \supset X_S^* </tex> <br/>
+
1) <tex>X_S^+ \supset X_S^* </tex> <br>
<tex>A \subset X_S^* => X \to A</tex>(по правилу расщепления, т.к. <tex>X_S^*</tex> изначально содержит в себе <tex>X</tex>) <tex>=> X \to B </tex>, то есть <tex>B</tex> входит в замыкание. </br>
+
<tex>A \subset X_S^* => X \to A</tex>(по правилу расщепления, так как <tex>X_S^*</tex> изначально содержит в себе <tex>X</tex>) <tex>=> X \to B </tex>, то есть <tex>B</tex> входит в замыкание. <br>
 
2) <tex>X_S^+ \subset X_S^* </tex> <br/>
 
2) <tex>X_S^+ \subset X_S^* </tex> <br/>
Доказательство от обратного: Пусть <tex>X_S^+ \not\subset X_S^* => \exists A: A \in X_S^+ \text{ and } A \not\in X_S^*.\; A \in X_S^+ => X \to A =></tex> есть вывод <tex> X \to X_1^+, ..., X_n^+ \to A</tex>. В этой цепочке найдём первую свежую ФЗ, то есть она не была в базовых ФЗ <tex>X</tex>. Такая фз точно есть в этой цепочке, например, <tex>X_n^+ \to A</tex>, т.к. <tex>A \in X_S^+ \text{ and } A \not\in X_S^* => </tex> такое правило не могло быть в <tex>X</tex>.  
+
Доказательство от обратного: Пусть <tex>X_S^+ \not\subset X_S^* => \exists A: A \in X_S^+ \text{ and } A \not\in X_S^*.\; A \in X_S^+ => X \to A =></tex> есть вывод <tex> X \to X_1^+, ..., X_n^+ \to A</tex>. В этой цепочке найдём первую свежую ФЗ, то есть она не была в базовых ФЗ <tex>X</tex>. Такая функциональная зависимость точно есть в этой цепочке, например, <tex>X_n^+ \to A</tex>, так как <tex>A \in X_S^+ \text{ and } A \not\in X_S^* => </tex> такое правило не могло быть в <tex>X</tex>. Получается, что атрибут A не был добавлен в <tex>X^*_S</tex> в алгоритме, такое может быть только если атрибут A уже содержался в <tex>X => </tex> противоречие.  
 
}}
 
}}
  
Строка 55: Строка 54:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Множество ФЗ <tex>S</tex> '''минимально по вклюючению''', если ни одна функциональная зависимость из множества <tex>S</tex> не может быть удалена из
+
Множество ФЗ <tex>S</tex> '''минимально по включению''', если ни одна функциональная зависимость из множества <tex>S</tex> не может быть удалена из
 
множества <tex>S</tex> без изменения его замыкания <tex>S^+</tex>.
 
множества <tex>S</tex> без изменения его замыкания <tex>S^+</tex>.
 
}}
 
}}
Строка 63: Строка 62:
 
|statement=Для любого множества ФЗ существует эквивалентное неприводимое множество ФЗ (НМФЗ).
 
|statement=Для любого множества ФЗ существует эквивалентное неприводимое множество ФЗ (НМФЗ).
 
|proof= Доказательство по построению: <br>
 
|proof= Доказательство по построению: <br>
* По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, т.к. старая ФЗ может быть получена по правилу объединения.  
+
* По правилу расщепления делаем все части единичными. Понятно, что замыкание множества ФЗ от такой операции не изменится, так как старая ФЗ может быть получена по правилу объединения.  
* Для левой части каждого правила пытаемся удалить по одному атрибуту <tex>A \cup \{X\} \to B</tex>. Если <tex>B \subset A^+_S</tex> выполняется, то <tex>A \to B</tex>, то можно минимизировать левую часть, отбросив <tex>X</tex>.
+
* Для каждого правила пытаемся минимизировать по включению левую часть всеми возможными способами. Чтобы проверить, что атрибут X можно удалить из <tex>A \cup \{X\} \to B</tex>, нужно проверить, что если <tex>B \subset A^+_S</tex> выполняется, то <tex>A \to B</tex>, то можно минимизировать левую часть, отбросив <tex>X</tex>. Потенциально из одной ФЗ может получиться множество ФЗ, где левая часть минимальна по включению.
* Пытаемся удалить по одному правилу <tex>A \to B</tex>. Если <tex>B \subset A^+_S\\\{A -> B\} \to B</tex> выполняется, то по теореме <tex>A \to B \in S^+</tex>, значит от этого правила можно избавится.
+
* Пытаемся удалить по одному правилу <tex>A \to B</tex>. Если <tex>B \subset A^+_{S\backslash\{A \to B\}} \to B</tex>, то по теореме <tex>A \to B \in S^+</tex>, значит это правило можно удалить.
 
}}
 
}}
  
=== Оценка времени построения ===  
+
=== Оценка времени построения НМФЗ ===  
 
* Расщепление правых частей - линейно по размеру правых частей.
 
* Расщепление правых частей - линейно по размеру правых частей.
 
* Удаление атрибута <tex>A \cup \{X\} \to B</tex>. На данном этапе из одной ФЗ возможно получить множество ФЗ минимальных по включению. Синтетическая оценка множества потенциальных множеств минимальных по включению мощностью <tex> {\frac {n}{2}}</tex> это  <tex>{\binom {n}{{\frac {n}{2}}}} \approx 2^n </tex>. То есть на ФЗ с большой левой частью возможен экспоненциальный рост количества ФЗ с минимальной по включению левой частью. Но на реальных данных большая левая часть в ФЗ практически не встречается.  
 
* Удаление атрибута <tex>A \cup \{X\} \to B</tex>. На данном этапе из одной ФЗ возможно получить множество ФЗ минимальных по включению. Синтетическая оценка множества потенциальных множеств минимальных по включению мощностью <tex> {\frac {n}{2}}</tex> это  <tex>{\binom {n}{{\frac {n}{2}}}} \approx 2^n </tex>. То есть на ФЗ с большой левой частью возможен экспоненциальный рост количества ФЗ с минимальной по включению левой частью. Но на реальных данных большая левая часть в ФЗ практически не встречается.  
* Удаление правила <tex>A \to B</tex>
+
* Удаление правила <tex>A \to B</tex>. На этом этапе не добавляем ФЗ, а только удаляем, поэтому сложность этот этап не добавит. Заметим, что каждую ФЗ на этом этапе можно рассматривать лишь один раз, так как все операции по приведению множества к неприводимому сохраняют исходное замыкание ФЗ.
 
 
=== Пример построения ===
 
Дано: <br>
 
* <tex>LId \to Lecturer \; Phone</tex>
 
* <tex>Lecturer \to Phone </tex>
 
* <tex>LId \to DeptHead</tex>
 
* <tex>Lecturer \; Phone \; Table \to DeptHead </tex>
 
Неприводимое множество ФЗ: <br>
 
* <tex>LId \to Lecturer</tex> - расщепили 1-ю ФЗ, при этом <tex>LId \to Phone</tex> не понадобится, т.к. выводится из <tex>LId \to Lecturer \to Phone</tex>
 
* <tex>Lecturer \to Phone </tex>
 
* <tex>LId \to DeptHead </tex>
 
* <tex>Lecturer \; Table \to DeptHead </tex> - т.к.
 
  
=== Выводы о НМФЗ ===
+
=== Замечания о НМФЗ ===
 
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
 
* Неприводимые множества ФЗ обычно много меньше множеств исходного множества ФЗ.
 
* Неприводимое множество ФЗ может не являться минимальным по мощности.
 
* Неприводимое множество ФЗ может не являться минимальным по мощности.

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

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

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

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

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