Osnove podatkovnih baz

Osnove podatkovnih baz - vaje 2.4.2020

Normalizacija

Dana je relacija $R(S)$ z množico atributov $S$ in funkcijskimi odvisnostmi oblike $X \to A$, kjer je $X \subseteq S$ in $A \in S$.

Lastnosti funkcijskih odvisnosti:

Refleksivnost: $A \in X \Rightarrow X \to A$
Tranzitivnost: $(\forall A \in Y: X \to A) \land Y \to B \Rightarrow X \to B$
Povečanje: $X \to A \Rightarrow XB \to A$

Ključi:

Množica $K \subseteq S$ je nadključ, če velja $K \to S$.
Množica $K \subseteq S$ je ključ, če je minimalen nadključ - tj., za vsak $A \in K$ velja $K \setminus {A} \not\to S$.

Normalne oblike:

3NF: za vsako funkcijsko odvisnost $X \to A$ velja
\[A \in X \quad \lor \quad X \text{ vsebuje ključ} \quad \lor \quad A \text{ je del ključa.}\]
BCNF: za vsako funkcijsko odvisnost $X \to A$ velja
\[A \in X \quad \lor \quad X \text{ vsebuje ključ.}\]

Naloga 1

Dana je relacija $R(ABCDE)$ s funkcijskimi odvisnostmi $A \to B$, $BC \to E$ in $DE \to A$. Najdi vse ključe za $R$. Ali je $R$ v 3NF/BCNF?

Izpeljane funkcijske odvisnosti:

\[\begin{aligned} A &\to B \\ BC &\to E \\ DE &\to A \\[1ex] AC &\to B \\ AC &\to C \\ AC &\to E \\[1ex] BCD &\to D \\[1ex] ACD &\to B \\ ACD &\to E \\[1ex] BCD &\to A \\ BCD &\to E \\[1ex] CDE &\to A \\ CDE &\to B \end{aligned}\]

Ključi: ACD, BCD, CDE

fun. odv.	3NF	BCNF
$A \to B$	ja	ne
$BC \to E$	ja	ne
$DE \to A$	ja	ne

$R$ je v 3NF, ni v BCNF.

Primer podatkov:

A	B	C	D	E
1	a	x	Q	Z’
1	a	y	R	W
2	a	x	S	Z’
2	a	z	S	Z

Anomalija spreminjanja: če popravimo Z v Z’ v stolpcu E prve vrstice, moramo to ponoviti še v tretji vrstici.

graph LR

R["R(AB*C*D*E)"] --- R1["R1(*AB)"]
R --- R2["R2(*B*CE)"]
R --- R3["R3(A*D*E)"]

V SQL lahko za to poskrbimo z določilom ON UPDATE CASCADE pri določitvi tujih ključev.

Naloga 2

Imejmo sledeče atribute z ER diagrama letališčne baze:

oznaka	opis
D	datum kontrole
E	EMŠO tehnika
I	ime testa
K	kapaciteta letala
M	model letala
O	dosežena ocena pri kontroli
P	plača tehnika
R	reg. št. letala
S	oznaka specializacije
T	test

Določi funkcijske odvisnosti med zgornjimi atributi, če lahko test na nekem letalu izvaja samo tisti tehnik, ki je specialist za model letala.

Pretvori shemo v 3NF. Ali se sklada s shemo, dobljeno iz ER diagrama?

\[\begin{aligned} E &\to P & \text{ok} \\ T &\to I & \text{ok} \\ M &\to K & \text{ok} \\ R &\to M & \text{ok} \\ S &\to E & \text{3NF ok} \\ S &\to M & \text{ok} \\ EM &\to S & \text{3NF ok} \\ DERT &\to O & \text{BCNF} \\[1ex] DRT &\to IKM \\ DERT &\to IKMOPS \\ DRST &\to EIKMOP \end{aligned}\]

Ključi: DERT, DRST

graph LR

R["R(*D*EMO*R*T) kontrola"]
R --- R2["R2(I*T) test"]
R --- R4["R4(M*R) letalo"] --- R3["R3(K*M) model"]
R --- R6["R6(*E*MS) specialist"]--- R5["R5(EM*S) specialist"]
R6 --- R1["R1(*EP) tehnik"]
R6 --- R3

Naloga 3

Dane so sledeče podrelacije relacije $R(ABCDEFGHI)$ skupaj s funkcijskimi odvisnostmi.

$R_1(ABCDE)$, $A \to B$, $C \to D$
$R_2(ABF)$, $AC \to E$, $B \to F$
$R_3(AD)$, $D \to G$, $G \to H$
$R_4(DCGH)$, $A \to I$, $I \to A$
$R_5(ACEI)$

Za vsak primer ugotovi, ali je podrelacija v BCNF, in če ni, jo pretvori v BCNF.

Ključ: ACE

graph LR

R["R(*A*C*E)"] --- R1["R1(*AB)"]
R --- R2["R2(*CD)"]

Ključ: AB

graph LR

R["R(*A*B)"] --- R1["R1(*BF)"]

3., 4., 5. so v BCNF.

Naloga 4

Dana je relacija $R(ABCD)$ in sledeče množice funkcijskih odvisnosti.

$C \to D$, $C \to A$, $B \to C$
$B \to C$, $D \to A$
$ABC \to D$, $D \to A$
$A \to B$, $BC \to D$, $A \to C$
$AB \to C$, $AB \to D$, $C \to A$, $D \to B$

Za vsako ugotovi, v kateri normalni obliki je $R$, in jo pretvori v BCNF.

Ključ: B; ni v 3NF

graph LR

R["R(*BC)"] --- R1["R1(A*CD)"]

Ključ: BD; ni v 3NF

graph LR

R["R(*B*D)"] --- R1["R1(*BC)"]
R --- R2["R2(A*D)"]

Ključa: ABC, BCD; je v 3NF, ni v BCNF

graph LR

R["R(*A*B*CD)"] --- R1["R1(A*D)"]

Ključ: A, ni v 3NF

graph LR

R["R(*ABC)"] --- R1["R1(*B*CD)"]

Ključi: AB, AD, BC, CD; je v 3NF, ni v BCNF

graph LR

R["R(*A*BCD)"] --- R1["R1(A*C)"]
R --- R2["R2(B*D)"]

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.