10 - decomposizioni che preservano le dipendenze

bisogna formalizzare il concetto di decomposizione che preserva un insieme di dipendenze funzionali.

definizione di decomposizione

Sia $R$ uno schema di relazione. Una decomposizione di $R$ è una famiglia $\rho =\{R_1,R_2,\dots R_k\}$ di sottoinsiemi di $R$ che ricopre $R$, ovvero: ${\bigcup }_{i=1}^k{R}_i=R$

• essenzialmente, decomporre $R$ significa definire dei sottoschemi che contengono ognuno un sottoinsieme degli attributi di $R$.

La proiezione di $F$ su un certo elemento $R_i$ contiene:

• le dipendenze funzionali di $F^{+}$la cui unione di determinante e determinato fa parte di $R_i$ (quindi le dipendenze con elementi in $R_i$)

Visto che due insiemi di dipendenze si possono scambiare quando hanno la stessa chiusura, una decomposizione preserva $F$ se la chiusura di $F$ è uguale alla chiusura dell’insieme $G=\{\text{unione delle proiezioni di F sui vari }{R}_i\}$.

equivalenza tra due insiemi di dipendenze funzionali

Siano $F$ e $G$ due insiemi di dipendenze funzionali. $F$ e $G$ sono equivalenti $(F\equiv G)$ se $F^{+}=G^{+}$.

• ovvero non sono uguali ma hanno la stessa chiusura.

lemma 2

Siano $F$ e $G$ due insiemi di dipendenze funzionali. $F\subseteq G^{+}⟺F^{+}\subseteq G^{+}$.

dimostrazione $F\subseteq G^{+}⟹F^{+}\subseteq G^{+}$

Sia $f\in F^{+}-F$ (una dipendenza di $F^{+}$ che non compare in $F$).

• noi sappiamo che ogni dipendenza funzionale in $F$ è derivabile da $G$ mediante gli assiomi di Armstrong (perché $F\subseteq G^{+}$, e $G^{+}=G^A$, quindi le dipendenze di $F$ sono dipendenze di $G^A$)
• anche $F^{+}(=F^A)$ (e quindi $f\in F^{+}$) è derivabile da $F$ tramite gli assiomi di Armstrong.
• quindi, si ha $G\stackrel{A}{\to }F\stackrel{A}{\to }{F}^A=F^{+}$
  • (ottengo $F$ da $G$ mediante Armstrong e poi, sempre mediante Armstrong, anche $F^A=F^{+}$.)
  • Il punto cruciale è che, applicando solo gli assiomi di Armstrong su un sottoinsieme di $G$, non “esco” mai da $G^{+}=G^A$
• quindi, $f\in F^{+}-F$ è derivabile da $G$ con gli assiomi di Armstrong, e $F^{+}\subseteq G^{+}$

preservare le dipendenze

definizione

Sia $R$ uno schema di relazione, $F$ un insieme di dipendenze funzionali su $R$, e $\rho =\{R_1,R_2,\dots ,R_K\}$ una decomposizione di $R$. Diciamo che $\rho$ preserva $F$ se: $F\equiv {\bigcup }_{i=1}^k{\pi }_{Ri}(F)$ dove ${\pi }_{Ri}(F)=\{X\to Y\mid X\to Y\in F^{+}\wedge XY\subseteq R_i\}$

• ogni ${\pi }_{Ri}$ è un insieme di dipendenze funzionali dato dalla proiezione di $F$ su $R_i$
  • proiettare un insieme di dipendenze su un sottoschema significa prendere tutte e sole le dipendenze in $F^{+}$ che hanno tutti gli attributi in $R_i$

verifica

Supponiamo di avere una decomposizione e voler verificare se preserva le dipendenze funzionali. Questo corrisponde a verificare che $G\equiv F$, ovvero che $G^{+}\subseteq F^{+}$ e che $F^{+}\subseteq G^{+}$.

utilità del lemma 2 per la verifica

Grazie al lemma 2, per verificare che $F^{+}=G^{+}$ mi basta verificare che $F\subseteq G^{+}$ e che $G^{+}\subseteq F$.

La verifica di $G\subseteq F^{+}$ è superflua, perché tutti gli elementi di $G$ sono necessariamente in $F^{+}$

• (infatti $G$ è definito come l’unione della proiezione di $F$ sulle varie decomposizioni, quindi l’unione di tutte le dipendenze di $F^{+}$ che hanno determinante e dipendente in $R_i$ → è possibile che in $G$ non ci siano alcune dipendenze di $F^{+}$, ma non il contrario)

Quindi, bisogna solo verificare che $F\subseteq G^{+}$.

Grazie al lemma 1, mi basta verificare che $\forall X\to Y\in F,Y\subseteq X_G^{+}$

Si può fare con l’algoritmo che segue:

• basta verificare che una sola dipendenza non appartiene alla chiusura di G per affermare che l’equivalenza non sussiste

algoritmo

• input - due insiemi $F$, $G$ di dipendenze funzionali su $R$
• output - la variabile successo, che indica se $F\subseteq G^{+}$

$$\begin{array}{rl}& \text{begin}\\ & \text{successo}:=true\\ & \text{for every }X\to Y\in F\\ & \text{do}\\ & \text{begin}\\ & \text{calcola }{X}^{+}\\ & \text{if }Y\not\subset X_G^{+}\text{ then successo}:=false\\ & \text{end}\\ & \text{end}\end{array}$$

• se $Y\not\subset X_G^{+}$, allora $X\to Y\notin G^A$ per il lemma, ovvero $X\to Y\notin G^{+}$ per il Teorema

basta fare i controlli solo per le dipendenze “a cavallo” - quelle che hanno sia determinante che dipendente in una decomposizione sono rispettate per forza

Nasce un problema: come calcoliamo $X_G^{+}$? Potremmo usare l’algoritmo per il calcolo della chiusura di un insieme di attributi, ma dovremmo prima calcolare $G$, e quindi $F^{+}$, il che richiederebbe tempo esponenziale.

Per questo, esiste un algoritmo:

calcolo della chiusura di X rispetto a G a partire da F

• input - uno schema $R$, un insieme $F$ di dipendenze funzionali su $R$, una decomposizione $\rho =\{R_1,R_2,\dots ,R_k\}$, un sottoinsieme $X$ di $R$.
• output - la chiusura di $X$ rispetto a $G={\cup }_{i=1}^k{\pi }_{Ri}(F)$

$$\begin{array}{rl}& \text{begin}\\ & Z:=X\\ & S:=\varnothing \\ & \text{for }i:=1\text{ to }k\\ & \text{do}S:=S\cup (Z\cap R_i{)}_F^{+}\cap R_i\\ & \text{while }S\not\subset Z\\ & \text{do}\\ & \text{begin}\\ & Z:=Z\cup S\\ & \text{for }i:=1\text{ to }k\\ & \text{do}S:=S\cup (Z\cap R_i{)}_F^{+}\cap R_i\\ & \text{end}\\ & \text{end}\end{array}$$

• partendo da un sottoinsieme di attributi $X$ di $R$, per prima cosa definiamo $Z$ come $X$ stesso per riflessività.
• dopodiché, ad ogni iterazione: $S:=S\cup (Z\cap R_i{)}_F^{+}\cap R_i$fa:
  • prima l’interzezione tra $Z$ e $R_i$, per considerare solo gli elementi di $Z$ che riguardano quello specifico sottoinsieme
  • poi la chiusura di quell’intersezione rispetto ad $F$, per trovare tutti gli attributi che ci interessano (tutti quelli determinati da dipendenze in $F^{+}$)
  • dopodiché l’intersezione con $R_i$, perché dobbiamo tenere solo gli attributi che sono effettivamente in $R_i$ (per la questione dipendenze con det e dip in $R_i$)
  • e infine l’unione con l’accumulatore $S$, dove salviamo questo passo fatto per tutti i sottoinsiemi $R_i$
    • nota: ad ogni iterazione (prima dell’unione con $S$), potremo ottenere massimo $R_i$ stesso (per l’intersezione con $R_i$)
  • ho trovato quindi la chiusura rispetto a ogni singolo $R_i$, e quindi rispetto a $G$
  • quindi, avremo gli attributi che dipendono funzionalmente da $X$, anche se appartengono a sottoschemi in cui $X$ non è incluso - perché dipendono da attributi che si trovano nello stesso sottoschema di $X$ e dipendono da $X$, e anche in altri sottoschemi

esempio inventato del passo cruciale

$R=(A,B,C,D,E,H)$

• $R_1=(A,B),R_2=(C,D),R_3=(E,H)$

cerchiamo $(AE{)}_G^{+}$

• $Z=AE$
• il passo prima dell’unione con $S$:
  • $Z\cap R_1=A$
  • trovo $A_F^{+}$
  • $A_F^{+}\cap R_1\subseteq AB$
• poi aggiungo a $S$

(anche qui il latex dell’algoritmo rubato a flavio, che si diverte a fare queste cose)

dimostrazione

dimostrare che l’algoritmo funziona significa mostrare che, alla fine dell’algoritmo, $Z$ conterrà tutta e sola la chiusura di $X$ rispetto a $G$. Quindi, che $Z^f\subseteq X_G^{+}\wedge Z^f\supseteq X_G^{+}$.

Dimostriamo solo $Z^f\subseteq X_G^{+}$.

ricordiamo:

• $G={\cup }_{i=1}^k{\pi }_{R_i}(F)$, con ${\pi }_{R_i(F)}=\{X\to Y\mid X\to Y\in F^{+}\wedge XY\subseteq R_i\}$
• $S:=S\cup (Z\cap R_i{)}_F^{+}\cap R_i$ (passo fondamentale dell’algoritmo)

Si dimostra per induzione sui $i$ ($\forall i,Z^i\subseteq X_G^{+}$)

• caso base ($i=0$): $Z^0=X$, e $X\subseteq X^{+}$, quindi $Z^0\subseteq X_G^{+}$
• ipotesi induttiva: $Z^{i-1}\subseteq X_G^{+}$

passo induttivo: Sia $A\in Z^i-Z^{i-1}$ (aggiunto all’ultimo passo). Se $A$ è stato aggiunto, vuol dire che deve esistere un sottoschema $R_j$ della decomposizione tale che: $A\in (Z^{i-1}\cap R_j{)}_F^{+}\cap R_j$, ovvero $A\in (Z^{i-1}\cap R_j{)}_F^{+}\wedge A\in R_j$.

Abbiamo quindi:

• $(Z^{i-1}\cap R_j)\to A\in F^A=F^{+}$ (per il lemma 1 e teorema $F^{+}=F^A$).

Sappiamo che $A\in R_j$, ma anche $(Z^{i-1}\cap R_j)\subseteq R_j$. Notiamo quindi che la dipendenza $(Z^{i-1}\cap R_j)\to A$ ha sia determinante che dipendente in un sottoschema $R_j$, e quindi, per definizione di ${\pi }_{R_i(F)}=\{X\to Y\in F^{+}:XY\subseteq R_i\}$, appartiene a ${\pi }_{R_j}(F)$ e, per costruzione di $G={\bigcup }_{i=0}^n{\pi }_{R_i}(F)$, appartiene a $G$.

• quindi $(Z^{i-1}\cap R_j)\to A\subseteq G\subseteq G^{+}=G^A$

In più, $(Z^{i-1}\cap R_j)\subseteq Z^{i-1}$, e, per ipotesi induttiva $Z^{i-1}\subseteq X_G^{+}$. Quindi si ha $(Z^{i-1}\cap R_j)\subseteq X_G^{+}$ (decomposizione) e, per il lemma 1, $X\to (Z^{i-1}\cap R_j)\in G^A$. Per transitività, da $X\to (Z^{i-1}\cap R_j),(Z^{i-1}\cap R_j)\to A\in G^A$, si ha $X\to A\in G^A$, cioè (l.1) $A\in X_G^{+}$.

abbiamo quindi dimostrato che $A\in Z^i⟹A\in X_G^{+}$, ovvero $Z^i\subseteq X_G^{+}\forall i$

domande orale

possibili domande

• cosa vuol dire che una decomposizione preserva un insieme di dipendenze?
• dimostrazione Lemma 2
• (forse) quali dipendenze bisogna controllare e quali no per l’algoritmo?
• dimostrazione calcolo di $X_G^{+}$ a partire da $F$