Decomposizione di schemi

Le anomalie possono essere risolte attraverso la decomposizione dello schema in schemi più piccoli.

Dato uno schema $R(T,F)$, si definisce come proiezione di $F$ su $Z\subseteq T$ l'insieme: $${\pi }_Z(F)=\left\{X\to Y\in F^{+}|X\cup Y\subseteq Z\right\}$$ attraverso cui si trova una decomposizione di $R(T,F)$, cioè un insieme di schemi $$\rho =\{R_1(T_1,F_1),...,R_n(T_n,F_n)\}$$ per cui ${\bigcup }_i{T}_i=T$ e $F_i={\pi }_{T_i}(F)$ filtrando per ogni $R_i$ le dipendenze con attributi coinvolti in $T_i\ne \varnothing$.

Per esempio su $R(ABCDE,\{AB\to CD,B\to E\})$ si risolvono le anomalie decomponendolo in:

• $R_1(ABCD,\{AB\to CD\})$
• $R_2(BE,\{B\to E\})$

Algoritmo

Il calcolo della proiezione ${\pi }_{T_i}(F)$ avviene dal:

1. Iniziare con l'insieme $P=\varnothing$
2. Per ogni $X\subset T_i$ trovare $Y=X_F^{+}\setminus X$
3. Aggiungere a $P$ la dipendenza $X\to (Y\cap T_i)$

Esempio

Per esempio su ${\pi }_{AB}(\{A\to B,B\to C,C\to A\})$, si ha:

1. L'insieme delle proiezioni iniziale è $P=\varnothing$
2. Si trovano le $X\subset AB$ da usare dall'insieme delle parti di $AB$
3. Per $X=A$ si trova $Y=A_F^{+}\setminus A=BC$
4. A $P$ si aggiunge $A\to (BC\cap AB)=A\to B$
5. Per $X=B$ si trova $Y=B_F^{+}\setminus B=AC$
6. A $P$ si aggiunge $B\to (AC\cap AB)=B\to A$

Preservazione dei dati

Per dire che la decomposizione preservi i dati, si deve avere che: $$r={\pi }_{T_1}(r)\bowtie ...\bowtie {\pi }_{T_n}(r)$$ per ogni istanza $r$ di $R(T,F)$, assicurandosi che dalle tabelle decomposte si ricavino gli stessi dati di $r$.

Per verificare che una decomposizione $\rho =\{R_1(T_1,F_1),R_2(T_2,F_2)\}$ preservi i dati basta verificare che $$T_1\cap T_2\to T_1\in F^{+}\vee T_1\cap T_2\to T_2\in F^{+}$$ trovando la chiusura $(T_1\cap T_2{)}_F^{+}$ e verificando che contenga $T_1$ o $T_2$.

Per esempio, con $R(ABCD,\{A\to BC\})$ si trova $T_1=ABC$, $T_2=AD$ e $A_F^{+}=ABC=T_1$.

Preservazione delle dipendenze

Per dire che la decomposizione preservi le dipendenze, si deve avere che: $$G=\bigcup _i{\pi }_{T_i}(F)\equiv F$$

Algoritmo

Per verificare che le dipendenze siano preservate basta assicurarsi che $Y\subseteq X_G^{+}$, per ogni $X\to Y\in F$.

Mentre $X_G^{+}=X_{{\bigcup }_i{\pi }_{T_i}(F)}^{+}$ si può ricavare con:

1. Iniziare con l'insieme $Z=X$
2. Trovare tutti gli schemi $R_i(T_i,F_i)\in \rho$
3. Aggiungere a $Z$ gli attributi $(Z\cap T_i{)}_F^{+}\cap T_i$
4. Ripetere finchè $Z$ viene aggiornato

Esempio

Per esempio se $F=\{A\to B,B\to C,C\to A\}$ e $\rho =\{R_1(AB),R_2(BC)\}$, si ha:

1. Verifica che $B\subseteq A_G^{+}$
   1. L'insieme iniziale è $Z=A$ e il primo schema è $R_1(AB)$
   2. A $Z$ si aggiunge $(Z\cap T_1{)}_F^{+}\cap T_1=(A\cap AB{)}_F^{+}\cap AB=ABC\cap AB=AB$
   3. Il prossimo schema è $R_2(BC)$
   4. A $Z$ si aggiunge $(Z\cap T_2{)}_F^{+}\cap T_2=(AB\cap BC{)}_F^{+}\cap BC=ABC\cap BC=BC$
   5. Quindi è verificato perchè $B\subseteq Z=ABC$
2. Verifica che $C\subseteq B_G^{+}$
   1. L'insieme iniziale è $Z=B$ e il primo schema è $R_1(AB)$
   2. A $Z$ si aggiunge $B_F^{+}\cap AB=AB$
   3. Il prossimo schema è $R_2(BC)$
   4. A $Z$ si aggiunge $B_F^{+}\cap BC=BC$
   5. Quindi è verificato perchè $C\subseteq Z=ABC$
3. Verifica che $A\subseteq C_G^{+}$
   1. L'insieme iniziale è $Z=C$ e il primo schema è $R_1(AB)$
   2. A $Z$ si aggiunge ${\varnothing }_F^{+}\cap AB=\varnothing$
   3. Il prossimo schema è $R_2(BC)$
   4. A $Z$ si aggiunge $C_F^{+}\cap BC=BC$
   5. Il prossimo schema è $R_1(AB)$ di nuovo
   6. A $Z$ si aggiunge $B_F^{+}\cap AB=AB$
   7. Quindi è verificato perchè $A\subseteq Z=ABC$

Relazione tra dati e dipendenze

Data una decomposizione $p=\{R_1(T_1),...,R_n(T_n)\}$ di $R(T,F)$ che preserva le dipendenze e per cui esiste un $T_i$ superchiave di $R$ allora $p$ si dice che preserva anche i dati.