Chiusura di un Insieme di Attributi

Related

---

Introduzione

Quando si decompone uno schema R su cui è definito un insieme di dipendenze funzionali F per ottenere altri schemi in 3NF, è importante preservare tutte le dipendenze in $F^{+}$.

Quindi ci serve calcolare $F^{+}$, però questo procedimento può essere lungo visto che richiede tempo esponenziale rispetto alla cardinalità di R ($|R|$).

In realtà ci basta sapere se una dipendenza funzionale $X\to Y$ appartiene ad $F^{+}$, e possiamo farlo calcolando $X^{+}$ e verificando che $Y\subseteq X^{+}$, infatti per il lemma 1: $X\to Y\in F^A⟺Y\subseteq X^{+}$ e poi il teorema dimostra che $F^A=F^{+}$.

Inoltre il calcolo di $X^{+}$ può tornare utile per verificare che un insieme di attributi sia chiave di uno schema.

---

Calcolo Chiusura (Algo)

Il calcolo della chiusura di un insieme di attributi $X$ denotato come $X^{+}$ può essere fatto attraverso questo algoritmo.

\begin{flalign*} &Z:=X\\ &S:=\{A \mid Y\to V\in F,\,\, A\in V,\,\, Y\subseteq Z\}\\ \\ &\text{while } S\not\subset Z:\\ &\qquad\qquad Z:=Z\cup S\\ &\qquad\qquad S:=\{A \mid Y\to V\in F,\,\, A\in V,\,\, Y\subseteq Z\}\\ \end{flalign*}

Input

• R:Schema relazionale
• F:Insieme di dipendenze funzionali su $R$
• X:Un sottoinsieme di $R$

Output

• Z: Chiusura di $X$ rispetto ad $F$

Approfondimento

Inizialmente abbiamo che:

• $Z$ che è uguale ad $X$
• $S$ contiene i singoli attributi che compongono le parti a destra delle dipendenze funzionali la cui parte sinistra è in $Z$.

Quindi inizialmente in $S$ avremo gli attributi determinati da $X$ .

Poi aggiungiamo questi elementi a $Z$ e continuiamo a iterare sui nuovi insieme $Z$ .

Ci fermiamo quando $S$ non ha elementi “nuovi” rispetto a $Z$ .

---

Esempi

Aggiungere Esempi Migliori

Esempio 1

Notiamo che per ogni passaggio dobbiamo sempre far partire la catena di operazioni da $AB$ .

È quindi più semplice vedere cosa abbiamo in $Z$ e “combinando” i pezzi vedere cosa possiamo ottenere.

Adesso dobbiamo dimostrare che l’algoritmo è corretto, ovvero che calcola correttamente la chiusura di un insieme di attributi $X$ rispetto ad un insieme $F$ di dipendenze funzionali.

---

Dimostrazione

Aggiungi dimostrazioneeeeeee