Algoritmi per esercizi

Regole di inferenza fondamentali

(IR1) Regola riflessiva: ****se $X \supseteq Y$ allora $X \to Y$
(IR2) Regola incrementale: $X \to Y \models XZ \to YZ$
(IR3) Regola transitiva: $\{X \to Y, Y \to Z\} \models X \to Z$
(IR4) Regola di decomposizione: $\{X \to YZ\} \models X \to Z$
(IR5) Regola di unione: $\{X\to Y, X \to Z\} \models X \to YZ$
(IR6) Regola pseudotransitiva: $\{X \to Y, WY \to Z\} \models WX \to Z$

Algoritmo di copertura minimale

porre $G := F$
rimpiazzare ogni dipendenza funzionale $X \to \{A_1,..,A_n\}$ in $G$ con $n$ dipendenze funzionali $X \to A_1,..,X\to A_n$
per ogni dipendenza funzionale $X\to A$ in $G$
```
  per ogni attributo $B$ che è un elemento di $X$
```
{

se $\{\{G \backslash\{X \to A\}\} \cup \{(X \backslash \{B\}) \to A\}\}$ è equivalente a $G$

allora sostituire $X \to A$ con $(X \backslash\{B\}) \to A$ in $G$

}
per ogni dipendenza funzionale rimanente $X \to A$ in $G$

{

se $\{G \backslash\{X\to A\}\}$ è equivalente a $G$

allora rimuovere $X\to A$ da $G$

}

</aside>

Test della proprietà di LJ

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$
porre $S(i,j) = b_{ij}$ per tutte le entrate della matrice

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$

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

se una riga contiene solo simboli $a$

allora la decomposizione ha la proprietà di lossless join

altrimenti no

</aside>

Algoritmo di decomposizione LJ e dependency preserving in 3NF

trovare una copertura minimale $G$ per $F$
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
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$

porre $K := R$
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>