30 Ott Basi di dati 1

---

---

Come calcolare $X^{+}$

Condizione di fermata: quando $S$ è completamente contenuto in $Z$.

dkjlshjlashl dfljksalkj

Esempio

oss

Una chiusura non può essere vuota infatti riflessività non esiste una chiusura di attributi vuota.

Teorema

Teorema: L’Algoritmo ”$\text{Calcolo di }{X}^{+}$ calcola correttamente la chiusura di un insieme di attributi $X$ rispetto ad un insieme $F$ di dipendenze funzionali.

Dimostrazione: Indichiamo con $Z^{(0)}$ il valore iniziale di $Z$ ($Z^{(0)}=X$) e con $Z^i$ ed $S^{(i)}$ ($i\ge 1$) i valori di $Z$ ed $S$ dopo l’i-esima esecuzione del corpo del ciclo; è facile vedere che $Z^{(i)}\subseteq Z^{(i+1)}$ per ogni $i$.

Teorema

$$A\in Z^{(j)}⟹A\in X^{+}$$

Dimostrazione per induzione: $Z^{finale}=X_F^{+}$ $Z^{finale}\subseteq X_F^{+}\wedge X_F^{+}\subseteq Z^{finale}$

$A\in Z^{finale}\iff A\in X_F^{+}$

il posso dell’induzione è basato sulle iterazioni del ciclo while

Caso base: $Z^0=xX\subseteq X^{+}⟹Z^0\subseteq X^{+}$

Ipotesi induttiva: $Z^{i-1}\subseteq X_F^{+}⟹x\to Z^{(i-1)}\in F^A$

Passo induttivo: $Z^i??$

oss: $A\in Z^i-Z^{i-1}$ questo significa che ha non era presente in $Z^{i-1}$ ma è presente in $Z^i$

$A\in Z^i-Z^{i-1}⟹\exists y\to W\in Ft.c.y\subseteq Z^{i-1}\wedge A\in W$

oss: $y\subseteq Z^{i-1}\underset{decomp}{⟹}X\to y\in F^A\underset{trans}{⟹}X\to W\in F^A⟹x\to A\in F^A\to A\in X_F^{+}$

Dimostrazione inversa

$$A\in X^{+}⟹A\in Z^{(G)}$$

Dimostrazione per induzione: $Z^{finale}=X_F^{+}$ $Z^{finale}\subseteq X_F^{+}\wedge X_F^{+}\subseteq Z^{finale}$

$A\in Z^{finale}\iff A\in X_F^{+}$

Example:

$R=(A,B,C,D,E,H$ $F=\{AB\to CD,EH\to D,D\to H\}$