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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Замыкание атрибутов)
(Неприводимые множества функциональных зависимостей)
Строка 48: Строка 48:
 
|definition=
 
|definition=
 
Множество ФЗ <tex>S</tex> '''неприводимо''', если: <br>
 
Множество ФЗ <tex>S</tex> '''неприводимо''', если: <br>
* Каждая правая часть ФЗ содержит один атрибут
+
* Каждая правая часть ФЗ содержит ровно один атрибут
 
* Каждая левая часть ФЗ минимальна по включению
 
* Каждая левая часть ФЗ минимальна по включению
 
* <tex>S</tex> минимально по включению
 
* <tex>S</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> - т.к.

Версия 11:57, 29 декабря 2020

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

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

[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] входит в замыкание. </br> 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].
[math]\triangleleft[/math]

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

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



Пример построения

Дано:

  • [math]LId \to Lecturer \; Phone[/math]
  • [math]Lecturer \to Phone [/math]
  • [math]LId \to DeptHead[/math]
  • [math]Lecturer \; Phone \; Table \to DeptHead [/math]

Неприводимое множество ФЗ:

  • [math]LId \to Lecturer[/math] - расщепили 1-ю ФЗ, при этом [math]LId \to Phone[/math] не понадобится, т.к. выводится из [math]LId \to Lecturer \to Phone[/math]
  • [math]Lecturer \to Phone [/math]
  • [math]LId \to DeptHead [/math]
  • [math]Lecturer \; Table \to DeptHead [/math] - т.к.