algoritmo per il calcolo della chiusura di un insieme di attributi

È migliore dell’applicazione indiscriminata degli assiomi di Armstrong per calcolare $X^{+}$, ha complessità polinomiale.

Input: una schema di relazione $R$, un insieme $F$ di dipendenze funzionali su $R$, un sottoinsieme $X$ di $R$.

Output: la chiusura di $X$ rispetto ad $F$ (restituita nella variabile $Z$)

1. $Z:=X$ Inizialmente assegniamo $X$ stesso all’accumulatore di $X^{+}$ che useremo nel ciclo.
2. $S:=\{A\text{tale che}Y\to V\in F\wedge A\in V\wedge Y\subseteq Z\}$ Scegliamo $A$ in modo che sia determinata da un insieme di attributi appartenenti alla chiusura di $X$ come calcolata fino a questo momento; poi assegniamola a $S$.
3. while $S\not\subset Z$: Fermiamoci quando non si può scegliere un attributo $S$ in modo che non sia già nella chiusura di $X$.
   1. $Z:=Z\cup S$ Aggiungiamo $S$ alla chiusura di $X$.
   2. $S:=\{A\text{tale che}Y\to V\in F\wedge A\in V\wedge Y\subseteq Z\}$
4. return $Z$

Dimostrazione che l’algoritmo è corretto

todo pag. 9 del pdf 11