8 - chiusura di un insieme di attributi

cosa vogliamo ottenere?

Quando si decompone uno schema di relazione R su cui è definito un insieme di dipendenze funzionali F, oltre ad ottenere schemi 3NF occorre:

• preservare le dipendenze
• poter ricostruire tramite join tutta e sola l’informazione originaria.

Le dipendenze funzionali che si vogliono preservare sono tutte quelle che sono soddisfatte da ogni istanza legale di R - le dipendenze funzionali in $F^{+}$.

Vogliamo quindi calcolare $F^{+}$, ma questo richiede tempo - è sufficiente avere un metodo per decidere se una dipendenza funzionale $X\to Y\in F^{+}$. Questo può essere fatto calcolando $X^{+}$ e verificando se $Y\subseteq X^{+}$. Infatti, ricordiamo il lemma 1 $X\to Y\in F^A⟺Y\subseteq X^{+}$ e il teorema che dimostra che $F^A=F^{+}$.

calcolare $F^{+}=F^A$ richiede tempo esponenziale

Basta considerare gli assiomi di riflessività o aumento o decomposizione: ogni sottoinsieme di $R$ porta a una o più dipendenze e i possibili sottoinsiemi di $R$ sono $2^{\#R}$

come calcolare $X^{+}$

per il calcolo di $X^{+}$ possiamo usare il seguente algoritmo:

• input: uno schema di relazione $R$, un insieme $F$ di dipendenze funzionali su $R$, e un sottoinsiee $X$ di $R$
• output: la chiusura di $X$ rispetto a $F$ (nella variabile $Z$)

algoritmo:

$$\begin{array}{rl}& \text{begin}\\ & Z:=X\\ & S:=\{A\mid Y\to V\in F,A\in V,Y\subseteq Z\}\\ & \text{while }S\not\subset Z\\ & \text{do}\\ & \text{begin}\\ & Z:=Z\cup S\\ & S:=\{A\mid Y\to V\in F,A\in V,Y\subseteq Z\}\\ & \text{end}\\ & \text{end}\end{array}$$

(latex algoritmo rubato a flavio con piccoli cambiamenti)

• per prima cosa, si definisce $Z$ come $X$ stessa (infatti, per riflessività, come minimo $X\to X$)
• poi si definisce $S$, un accumulatore per i nuovi attributi, come $S:=\{A\text{ t.c. }Y\to V\in F\wedge A\in V\wedge Y\subseteq Z\}$ quindi, partendo da $Z=X$, cerco una dipendenza $Y\to V$ con $Y\subseteq Z$ (quindi che abbia come determinante un pezzo di $X$) e metto nell’accumulatore ogni $A$ elemento del dipendente. Dire $Y\subseteq X$ vuol dire $X\to Y$ (riflessività), perciò, per transitività, $X\to Y,Y\to V⟹X\to V$

Essenzialmente, $S$ prende le dipendenze con un determinante contenuto in $X$ e le mette nella sua chiusura.

• dopodiché, controlla se ha aggiunto cose nuove a $S$ (ovvero se $S\not\subset Z$) :
  • se ha aggiunto nuove dipendenze, ridefinisce $Z$ come $Z\cup S$ (aggiunge l’accumulatore a $Z$) e riapplica l’algoritmo (perché le nuove aggiunte possono essere usate per trovare altre dipendenze)
  • altrimenti,vuol dire che ha finito di trovare altre dipendenze e $Z$ è completo

slide algoritmo

esempio

$R=ABCDEH$ $F=\{AB\to CD,EH\to D,D\to H\}$ $A{B}^{+}=ABCDH$

teorema: l’algoritmo è corretto

L’algoritmo “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$, con $i\ge 1$, i valori di $Z$ e $S$ dopo l’i-esima esecuzione del corpo del ciclo. È facile vedere che $Z^i\subseteq Z^{i+1}$

Sia $j$ tale che $Z^j$ è $Z^{\text{finale}}$, ovvero $Z$ al termine dell’algoritmo. Quindi $S(j)\subseteq Z(j)$. Dobbiamo provare $A\in Z^j⟺A\in X^{+}$

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

Si dimostra per induzione.

• caso base: $Z^0=X$, per riflessività $X\subseteq X^{+}$, quindi $X\subseteq X^{+}⟹Z^0\subseteq X^{+}$
• ipotesi induttiva: poniamo per ipotesi induttiva che $Z^{i-1}\subseteq X^{+}$
  • (ricordiamo che per il lemma 1 abbiamo quindi: $X\to Z^{i-1}\in F^A$)

passo induttivo

Prendiamo $A\in Z^i-Z^{i-1}$, ovvero aggiunto all’ultimo passo. Vuol dire che $A$ è stato aggiunto perché $\exists Y\to W:Y\subseteq Z^{i-1}\wedge A\in W$ (a è determinato da qualcosa che si trovava in $Z^{i-1}$).

Per ipotesi induttiva, ho $Z^{i-1}\subseteq X^{+}$, quindi, per decomposizione ($Y\subseteq Z^{i-1}$) per il lemma 1, $X\to Y\in F^A$. Per transitività, da $X\to Y,Y\to W$ (che è in $F$ e quindi in $F^A$) ottengo $X\to W\in F^A$. Per il lemma 1, ho $W\in X^{+}$ e quindi $A\in X^{+}$.

quindi, visto che $A\in Z^i-Z^{i-1}\in X^{+}$ e per ipotesi induttiva $Z^{i-1}\in X^{+}$, ho dimostrato $Z^i\in X^{+}$

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

Sia $A\in X^{+}$. Sappiamo, per il lemma 1, che $X\to A\in F^A=F^{+}$ (per il teorema $F^A=F^{+}$).

Consideriamo la seguente istanza $r$ di $R$:

che ha due tuple uguali sugli attributi di $Z^j$ ($Z$ finale) e diverse su $R-Z^j$.

mostriamo che $r$ è un’istanza legale

Prendiamo una qualunque dipendenza funzionale $V\to W\in F$.

• se $V⊈Z^j$ (quindi $V\cap (R-Z^j)\ne \varnothing$) le tuple sono diverse su almeno un attributo di $V$, quindi la dipendenza è rispettata

Se $V\subseteq Z^j$ le due tuple avranno valori uguali su $W$. Infatti, se per assurdo avessimo $t_1[V]=t_2[V]$ ma $t_1[W]\ne t_2[W]$, ci sarebbe almeno un elemento di $W$ in $R-Z^j$. Questo è impossibile per come è definito l’algoritmo: $S:=\{A:V\to W\in F\wedge V\subseteq Z^{i-1}\wedge A\in W\}$ Vorrebbe dire che, applicando l’algoritmo, potrei ancora inserire nuovi elementi in $Z$ - ma questo è impossibile perché, per costruzione, $Z$ è finale. Quindi vuol dire che $W\cap R-Z^j$ è impossibile, e quindi la dipendenza è soddisfatta.

$r$ è quindi un’istanza legale (rispetta una qualsiasi dipendenza di $F$)

dimostriamo l’implicazione

Sappiamo che $X=Z^0\subseteq Z^j$, quindi le due tuple sono uguali su $X$. Visto che $r$ è un’istanza legale, deve soddisfare $X\to A\in F^{+}$, quindi lo saranno anche su $A$, il che implica $A\in Z^j$.

abbiamo quindi dimostrato anche $A\in F^{+}⟹A\in Z^j$

proprietà dell’insieme vuoto

• l’insieme vuoto $\varnothing$ è un sottoinsieme di ogni insieme A: $\forall A:A$
• l’unione di qualunque insieme $A$ con l’insieme vuoto è $A$ stesso: $\forall A:A\cup \varnothing =A$
• l’intersezione di qualunque insieme $A$ con l’insieme vuoto è l’insieme vuoto: $\forall A:A\cap \varnothing =\varnothing$
• il prodotto cartesiano di un qualunque insieme $A$ con l’insieme vuoto è l’insieme vuoto: $\forall A:A\times \varnothing =\varnothing$
• l’unico sottoinsieme dell’insieme vuoto è l’insieme vuoto stesso
• la cardinalità dell’insieme vuoto è zero: l’insieme vuoto è finito

domande orale

Question

• perché calcolare $F^{+}$ richiede tempo esponenziale?
• dimostrazione della correttezza dell’algoritmo per il calcolo di $X^{+}$