Copertura minima

Per calcolare una copertura minima di un insieme \( \mathcal{F} \) di d.f. su uno schema di relazione \( R \) bisogna eseguire 3 passi:

1. Trasformare \( \mathcal{F} \) in forma standard - f.s.
   ( Applicare la regola di decomposizione. Su tutte le d.f. di \( \mathcal{F} \) per portare il numero di attributi sul secondo membro di ogni d.f. ad 1)
2. Riduzione SX
   ( Ridurre le parti sinistre sulle d.f. per eliminare le ridondanze sugli attributi)
3. Eliminazione delle ridondanze
   ( Eliminare le risondanze sulle d.f. )

---

Sia assegnato uno schema di relazione \( R \) ed un insieme \( \mathcal{F} \) di d.f.
\( \rightarrow \) Determinare una copertura minima di \( \mathcal{F} \) e le chiavi candidate di \( R \) $$ \left\langle R(ABCDEFGHI), \mathcal{F} = \begin{pmatrix} ABC \rightarrow D \\ DE \rightarrow I \\ I \rightarrow ADF \\ EF \rightarrow C \\ F \rightarrow BG \\ G \rightarrow EH \\ H \rightarrow G \end{pmatrix} \right\rangle $$ Per ridurre le parti sinistre bisogna considerare tutte le d.f. in \( \mathcal{\hat{F}} \) che hanno a primo membro un numero superiore ad 1 di attributi nell'esempio consideriamo le d.f. \( \left\{ABC \rightarrow D, DE \rightarrow I, EF \rightarrow C \right\} \). Bisogna adesso cercare di eliminare nelle parti a sinistra di ogni d.f. quanti più attributi possibile. Per fare questo bisogna calcolare le chiusure sugli attributi a sinistra.
Consideriamo ad esempio la d.f. \( DE \rightarrow I \). in particolare concentriamoci sulla parte sinistra \( DE \). per ridurla dobbiamo verificare che eliminando ad esempio \( E \), la d.f. rimane equivalente cioè con il solo attributo \( D \) rimanente si riesce ad implicare \( E \), ottenendo quindi una forma equivalente per la d.f. \( DE \rightarrow I \). Analogo il caso se provassimo ad eliminare \( D \) e riuscissimo mediante il solo attributo \( E \) ad implicare \( D \) , potremmo concludere che \( DE \rightarrow I \equiv D \rightarrow I \).

In realtà non è necessario ridurre tutte le d.f., perchè molte sono irriducibili, e questa caratteristica si osserva ad esempio nella d.f. \( ABC \rightarrow D \). E' evidente che gli attributi \( ABC \) compaiono solo in questa d.f., risulta perciò essenziale. Se provassimo a ridurla a sinistra ci accorgeremmo che calcolando la copertura di \( ABC \) non arriveremmo da nessuna parte per i motivi sopra enunciati. Stesso discorso vale per \( DE \rightarrow I \)

Proviamo a ridurre quindi \( EF \rightarrow C \), in quanto la \( F \) compare in molte altre d.f. e può darsi che riusciamo a ridurne la parte sx. $$ F \rightarrow E ? \longrightarrow F^{+} = FBGH\underset{\uparrow}{E} $$ Siccome \( F \rightarrow E \), possiamo eliminare l'attributo \( E \) dalla parte sinistra ottenendo un d.f. equivalente \( \require{cancel} \bcancel{E}F \rightarrow C \) $$ F \rightarrow C \equiv EF \rightarrow C $$ Riassumendo, il nostro insieme di d.f. con le dovute riduzioni sugli attributi a sinistra diviene:

l'ultima fase consiste nella eliminazione di una o più d.f. dall'insieme, con la proprietà di ottenere via, via insiemi equivalenti. Dopo aver eliminato tutte le d.f. ridondanti, se proviamo ad eliminarne una ulteriore perdiamo informazione perchè abbiamo raggiunto una condizione di minimalità.

Come nel passo precedente dovremmo esaminare tutte le d.f. e per ogni d.f. \( X \rightarrow Y \) dovremmo calcolare $$ {\Large {\LARGE X}^{+}_{\mathcal{\hat{F}'} - \left\{ X \rightarrow Y \right\} } }$$ Per verificare se la d.f. \( (\heartsuit) X \rightarrow Y \) è ridondante dobbiamo vedere se con tutte le d.f. esclusa la \( (\heartsuit) \) riusciamo comunque ad implicare \( Y \) se così accade possiamo eliminare la \( (\heartsuit) \) dall'insieme \( \mathcal{\hat{F}'} \).

Come nel caso precedente possiamo evitare, osservando accuratamente le d.f., di calcolarci tutte le chiusure, ma solo quelle in cui almeno un attributo a sinistra o a destra compare altrove nelle d.f. rimanenti. Ad esempio sarebbe inutile provare la ridondanza sulla d.f. \( I \rightarrow A \) in quanto l'attributo \( A \) compare solo in questa d.f. (essa è necessaria), come anche la d.f. \( DE \rightarrow I \); (pur comparendo la \( I \) in altre d.f. lo stesso non accade per \( DE \) che compare solo nella d.f. corrente.

Calcoliamoci solo le chiusure essenziali:
nota bene: quando calcoli una chiusura la d.f. su cui stai valutando la ridondanza non va considerata nel calcolo della chiusura stessa. $$ {\Large {\LARGE D}^{+}_{\mathcal{\hat{F}'} - \left\{ I \rightarrow D \right\} } {\large = IAFBGC\underset{\underset{\times}{\uparrow}}{D}} }$$ $$ {\Large {\LARGE F}^{+}_{\mathcal{\hat{F}'} - \left\{ I \rightarrow D, F \rightarrow G \right\} } {\large = FBC} }$$

Finalmente otteniamo la nostra copertura minima compattata:

Chiavi

Una volta in possesso di una copertura minima di \( \mathcal{F} \), il calcolo delle chiavi risulta assai semplice. Bisogna costruire l'ipergrafo delle dipendenze. Le chiavi saranno tutti gli attributi che percorrono l'intero grafo.
$$ Keys(g) = \left\{ DE, I, DF, DG, AF, ABCE \right\} $$