Lossless join (LJ)

Una decomposizione con lossless join garantisce che non vengono generate tuple spurie applicando un’operazione di NATURAL JOIN alle relazioni nella decomposizione

<aside> <img src="/icons/exclamation-mark_purple.svg" alt="/icons/exclamation-mark_purple.svg" width="40px" />

Una decomposizione $D=\{R_1,..,R_m\}$ di $R$ ha la proprietà di lossless join rispetto all’insieme di dipendenze di $F$ su $R$ se per ogni stato di relazione $r$ di $R$ che soddisfa $F$ vale $^*(\Pi_{R_1}(r),..,\Pi_{R_m}(r)) = r$

</aside>

Test della proprietà di LJ

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. creare una matrice $S$ con una riga $i$ per ogni relazione $R_i$ nella decomposizione $D$ e una colonna $j$ per ogni attributo $A_j$ in $R$

2. porre $S(i,j) = b_{ij}$ per tutte le entrate della matrice

3. per ogni riga $i$ che rappresenta lo schema di relazione $R_i$

     per ogni colonna $j$ che rappresenta l’attributo $A_j$
   
     se $R_i$ include l’attributo $A_j$
   
     allora porre $S(i,j) =a_j$
   

4. ripetere quanto segue finché l’esecuzione del ciclo non modifica più $S$

     per ogni dipendenza funzionale $X \\to Y$ in $F$ 
   
     per tutte le righe in $S$ che hanno gli stessi simboli nelle colonne corrispondenti agli attributi in $X$
   
     rendere uguali i simboli in ogni colonna che corrispondono ad un attributo in $Y$ come segue
   
     se una riga ha un simbolo $a$ nella colonna, porre le altre righe allo stesso simbolo $a$ nella colonna
   

   se non esiste in nessuna riga un simbolo $a$ per l’attributo, scegliere uno dei simboli $b$ che appaiono in una delle righe e porre le altre righe a quel simbolo $b$ nella colonna

5. se una riga contiene solo simboli $a$

   allora la decomposizione ha la proprietà di lossless join

   altrimenti no

</aside>

Proprietà LJ1

Una decomposizione $D= \{R_1,R_2\}$ di $R$ ha la proprietà di lossless join rispetto a un insieme di dipendenze funzionali $F$ su $R$ se e solo se:

• la FD $((R_1 \cap R_2) \to (R_1 \backslash R_2) )$ è in $F^+$
• oppure la FD $((R_1 \cap R_2) \to (R_2 \backslash R_1))$ è in $F^+$

Proprietà LJ2

Se una decomposizione $D=\{R_1,..,R_m\}$ di $R$ ha la proprietà LJ rispetto a un insieme di FD $F$ su $R$, se se una decomposizione $D_1 = \{Q_1,..,Q_k\}$ di $R_i$ ha la proprietà LJ rispetto alla proiezione di $F$ su $R_i$, allora la decomposizione $D_2 =\{R_1,..,R_{i-1},Q_1,..,Q_k,R_{i+1},..,R_m\}$ di $R$ ha la priprietà LJ rispetto a $F$

Algoritmo di decomposizione LJ in BCNF

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. porre $D:=R$

2. finché c’è uno schema di relazione $Q$ in $D$ che non è in BCNF

   {

   si scelga uno schema di relazione $Q$ in $D$ che non sia in BCNF

   si trovi una dipendenza funzionale $X \to Y$ che violi BCNF

   si sostituisca $Q$ in $D$ con due schemi di relazione $(Q\backslash Y)$ e $(X \cup Y)$

   }

</aside>

Algoritmo di decomposizione LJ e dependency preserving in 3NF

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. trovare una copertura minimale $G$ per $F$
2. per ogni parte sinistra $X$ di una FD in $G$, creare uno schema di relazione in $D$ con attributi $\{X \cup A_1 \cup ..\cup A_m\}$ dove $X \to A_1,..,X\to A_m$ sono le sole dipendenze in $G$ aventi $X$ come parte sinistra
3. se nessuno degli schemi di relazione in $D$ contiene una chiave di $R$, creare un altro schema di relazione che contiene attributi che formano una chiave per $R$ </aside>

Trovare una chiave $K$ di $R$

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. porre $K := R$

2. per ogni attributo $A$ in $K$

   {

   calcolare $(K \backslash A)^+$ rispetto all’insieme di FD

   se $(K\backslash A)^+$ contiene tutti gli attributi in $R$

   allora $K =K \backslash \{A\}$

   }

</aside>

Valori null

Nessun valore null è ammesso per gli attributi di join

Sommario