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

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

|definition= Замыкание множества атрибутов [math]X[/math] над множеством ФЗ [math]S[/math] [math]S[/math] - максимальное по включению множество атрибутов [math]X^+_S[/math] функционально зависящих от [math]S[/math]. }}

Максимальный размер [math]X^+_S[/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-\gt X_1^+, ..., X_n^+ \to A [/math] TODO

[math]\triangleleft[/math]