Copertura Minimale

Related

• Calcolo di una Decomposizione
• Basi di Dati 1 (class)

---

Introduzione

Una copertura minimale è un insieme di dipendenze funzionali che è equivalente all’insieme originale di dipendenze funzionali, ma con il minimo numero di dipendenze funzionali necessarie per descrivere le relazioni tra gli attributi.

oss: Un insieme di dipendenze funzionali $F$, può avere più coperture minimali equivalenti. È proprio questo il motivo per cui l’algoritmo di decomposizione può produrre risultati diversi, ma tutti corretti.

---

Definizione

Sia $F$ un insieme di dipendenze funzionali. Una copertura minimale di $F$ è un insieme $G$ di dipendenze funzionali equivalente ad $F$ che rispetta queste 3 condizioni:

Condizione 1

Per ogni dipendenza funzionale in $G$ la parte destra è un singleton.

Importante: ogni attributo nella parte destra è non ridondante

Condizione 2

Per nessuna dipendenza funzionale $X\to A$ in $G$ esiste $X’\subset X$ tale che

$$G\equiv (G-\{X\to A\})\cup \{X^{\prime }\to A\}$$

Ovvero non accedere che:

• se a $G$ tolgo $X\to A$ e aggiungo $X^{\prime }\to A$

• dopo queste operazioni $G$ è restato invariato allora $X\to A$

Importante: ogni attributo nella parte sinistra è non ridondante

Condizione 3

Per nessuna dipendenza funzionale $X\to A$ in $G$ si ha che:

$$G\equiv G-\{X\to A\}$$

Ovvero: se a $G$ tolgo la dipendenza $X\to A$ e il “significato” di $G$ resta invariato allora $X\to A$ non va bene.

Importante: ogni dipendenza è non ridondante

---

Calcolo

Per ogni insieme di dipendenze funzionali $F$ esiste una copertura minimale equivalente ad $F$ che può essere ottenuta in tempo polinomiale in tre passi:

Passo 1

Usando la regola della decomposizione, le parti destre delle dipendenze funzionali vengono ridotte a singleton.

Ovvero: $A\to BC$ uguale ad $A\to B$ e $A\to C$

Passo 2

Ogni dipendenza funzionale $A_1\dots A_i{A}_{i+1}\dots A_n\to A$ in $F$ tale che:

$$F\equiv F-\{A_1\dots A_{i-1}{A}_i{A}_{i+1}\dots A_n\to A\}\cup \{A_1\dots A_{i-1}{A}_{i+1}\dots A_n\to A\}$$

Deve essere sostituita da $A_1\dots A_{i-1}{A}_{i+1}\dots A_n\to A$, se quest’ultima appartiene già ad $F$ la dipendenza originaria viene semplicemente eliminata, altrimenti il processo viene ripetuto ricorsivamente su $A_1\dots A_{i-1}{A}_{i+1}\dots A_n\equiv A$

Il passo termina quando nessuna dipendenza funzionale può più essere ridotta.

Passo 3

Ogni dipendenza funzionale $X\equiv A$ in $F$ tale che:

$$F\equiv F-\{X\to A\}$$

viene eliminata, in quanto risulta ridondante.

---

Verificare l’equivalenza $\equiv$

Il passo 2 ed il passo 3 richiedono la verifica dell’equivalenza tra due insiemi di dipendenze funzionali (Lemma 2).

Visto che ci troviamo in condizioni speciali vedremo che ci sono dei metodi semplificati per verificare l’equivalenza.

Verifica $\equiv$ in passo 2

Assumiamo che:

• F sia l’insieme di dipendenze funzionali
• G sia l’insieme di dipendenze funzionali “ridotto”

Notiamo che i due insieme sono identici tranne per una dipendenza

• F conterrà la dipendenza “originale” che chiameremo $X\to A$

• F conterrà la dipendenza “ridotta” che chiameremo $X^{\prime }\to A$

oss: $X^{\prime }\subset X$

Per verificare l’equivalenza tra F e G dobbiamo solo controllare che

• la dipendenza “originale” ($X\to A)$ si trovi in $G^{+}$

• la dipendenza “ridotta” ($X^{\prime }\to A)$ si trovi in $F^{+}$.

oss: non serve ricalcolare la chiusura di attributi di cui l’abbiamo già calcolata (non cambiano)

Esempio $F=\{AB\to C,A\to D,D\to C\}$

Verifichiamo: se è possibile rimuovere la $B$ da $AB\to C$, abbiamo che $G=\{A\to C,A\to D,D\to C\}$

Quindi dobbiamo verificare che:

• $A\to C\in F^{+}$
• $AB\to C\in G^{+}$

Per verificare che $A\to C\in F^{+}$ possiamo l’algoritmo per il calcolo della chiusura di un insieme di attributi inizializzando l’input $Z$ ad $Z=A$ e si applicando le dipendenze in $F$.

• una volta applicato l’algoritmo notiamo che $C\in A_F^{+}$ ✅

Per verificare che $AB\to C\in G^{+}$ possiamo l’algoritmo per il calcolo della chiusura di un insieme di attributi inizializzando l’input $Z$ ad $Z=AB$ e si applicando le dipendenze in $G$.

• Questo caso è molto banale infatti abbiamo che $G$ contiene $A\to C$ quindi è ovvio che $AB\to C$. ✅

Verifica $\equiv$ in passo 3

Assumiamo che:

• F sia l’insieme delle dipendenze funzionali che contiene la dipendenza $X\to A$

• G sia uguale ad $F$ ma $X\to A$ è stata rimossa

oss: Notiamo che i due insieme differiscono soltanto per una dipendenza e che $G\subset F$ quindi $G^{+}\subseteq F^{+}$

Quindi per verificare che $F\equiv G$ ci resta soltanto da controllare che $F^{+}\subseteq G^{+}$, che sarà sicuramente vero se $F\subseteq G^{+}$

Ma visto che $F$ e $G$ differiscono soltanto per $X\to A$ e basta verificare che $X\to A\in G^{+}$ ovvero che $A\in (X{)}_G^{+}$

oss: serve ricalcolare la chiusura di attributi di cui l’abbiamo già calcolata, infatti potrebbe cambiare

---

Esempi

Vedi altri esercizi qui

Esempio

Calcolare la copertura minimale di:

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