Lab 9

back

Link do IDroo: https://idroo.com/board-sVDidbHrLP

Zadanie 1

Dana relacja $R(ABCDEF)$ z zależnościami funkcyjnymi:
$$X = \{AB \rightarrow C, C \rightarrow E, D \rightarrow E, C \rightarrow D\}$$

Nadklucze: $\{ABCDEF, ABCDF, ABCEF, ABDEF, ABCF, ABDF, ABF\}$
Klucz: $ABF$

Normalizacja do 3NF:

Aby zminimalizować zbiór $X$ należy wyrzucić zależność $C \rightarrow E$, bo wynika ona z $C \rightarrow D$ oraz $D \rightarrow E$.

$$X' = \{AB \rightarrow C, D \rightarrow E, C \rightarrow D\}$$

Pozostałe zalezności już są minimalne, robimy więc relację dla każdej z nich:

$R_1 = (ABC, \{AB \rightarrow C\})$, klucz $AB$
$R_2 = (CD, \{C \rightarrow D\}))$, klucz $C$
$R_3 = (DE, \{D \rightarrow E\}))$, klucz $D$

No i brakuje nam relacji reprezentującej cały klucz.

$R_4 = (ABF, \{\})$, klucz $ABF$

Normalizacja do BCNF

Łatwo zauważyć, że wszystkie relacje uzyskane z normalizacji do 3NF są też w BCNF. Jako ćwiczenie, zobaczmy algorytm normalizacji do BCNF odpalony na $R$.

Najpierw liczymy $X^*$:
$$X^* = \{AB \rightarrow CDE, C \rightarrow DE, D \rightarrow E\}$$
Zależność $AB \rightarrow CDE$ narusza BCNF, bo $AB$ nie jest nadkluczem (nie implikuje $F$). W związku z tym dzielimy na dwie tabele:

$T_1 = (ABCDE, \{AB \rightarrow CDE, C \rightarrow DE, D \rightarrow E\})$
$T_2 = (ABF, \{\})$

Tabela $T_2$ jest już w BCNF, bo nie ma żadnych zależności funkcyjnych i cały zbiór kolumn jest jedynym kluczem. W tabeli $T_1$ nadkluczem jest teraz $AB$. W związku z tym zależnośc $C \rightarrow DE$ psuje BCNF, dzielimy więc $T_1$ na $T_3$ i $T_4$:

$T_2 = (ABF, \{\})$
$T_3 = (CDE, \{C \rightarrow DE, D \rightarrow E\})$
$T_4 = (ABC, \{AB \rightarrow C\})$

Dla $T_3$ kluczem jest $C$, więc ostatnim krokiem jest rozbicie $T_3$ przez zależność $D \rightarrow E$ na $T_5$ i $T_6$:

$T_2 = (ABF, \{\})$
$T_4 = (ABC, \{AB \rightarrow C\})$
$T_5 = (CD, \{C \rightarrow D\})$
$T_6 = (DE, \{D \rightarrow E\})$

Dostaliśmy te same tabele co dla 3NF-a, wszystkie zależności da się odzyskać.

Zadanie 2

Relacja $R(ABCDE)$ z zależnościami:
$$X = \{AB \rightarrow CD, C \rightarrow E, D \rightarrow E\}$$

Nadklucze: $\{ABCDE, ABCD, ABCE, ABDE, ABC, ABD, ABE, AB\}$
Klucz: $AB$

Normalizacja do 3NF

Minimalna reprezentacja $X$:
$$X' = \{AB \rightarrow C, AB \rightarrow D, C \rightarrow E, D \rightarrow E\}$$

Dzielimy na $4$ tabele:

$R_1 = (ABC, \{AB \rightarrow C\})$, klucz $AB$
$R_2 = (ABD, \{AB \rightarrow D\})$, klucz $AB$
$R_3 = (CE, \{C \rightarrow E\})$, klucz $C$
$R_4 = (DE, \{D \rightarrow E\})$, klucz $D$

Klucz jest zawarty zarówno w $R_1$ jak i w $R_2$, więc to już koniec.

Nie tracimy żadnych zależności, bo to głupie pytanie jest w ogóle: normalizacja do 3NF nigdy nie powoduje utraty zależności. Co więcej, dostaliśmy też BCNF na każdej tabeli.

Przy okazji widać tutaj pewien minus tego algorytmu: tabele $R_1$ i $R_2$ moglibyśmy połączyć i nadal mieć 3NF. Żeby zapobiec takiemu niepotrzebnemu dzieleniu tabel, które później będziemy musieli joinować, można nasze minimalne pokrycie $X$ przedefiniować: łączymy wszystkie takie zależności $X \rightarrow Y$, $X \rightarrow Z$, że $Y$ ani $Z$ nie należą do żadnego klucza. W tym przypadku połączylibyśmy $AB \rightarrow C$ i $AB \rightarrow D$ i dostalibyśmy tabelę $(ABCD, \{AB \rightarrow CD\})$. Dowód tego, że algorytm nadal działa i zwraca 3NF jest dość prosty.

Normalizacja do BCNF

Liczymy dopełnienie:
$$X^* = \{AB \rightarrow CDE, C \rightarrow E, D \rightarrow E\}$$

Zależność $C \rightarrow E$ łamie BCNF, dzielimy.

$T_1 = (CE, \{C \rightarrow E\})$
$T_2 = (ABCD, \{AB \rightarrow CD\})$

I to tyle, obie tabele są w BCNF. Straciliśmy jednak zależność $D \rightarrow E$. Ale halo, halo, przecież przed chwilą dostaliśmy schemat, który był w BCNF i nie tracił tej zależności! Morał: przed normalizacją do BCNF zawsze warto wykonać normalizację do 3NF. Dopiero kiedy po normalizacji do 3NF nie jesteśmy w BCNF odpalamy normalizację do BCNF.

back