Osnove podatkovnih baz

« nazaj

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.

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

---

Naloga 3

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

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

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

---

1. Ključ: ACE

2. Ključ: AB

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

---

Naloga 4

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

1. $C \to D$, $C \to A$, $B \to C$
2. $B \to C$, $D \to A$
3. $ABC \to D$, $D \to A$
4. $A \to B$, $BC \to D$, $A \to C$
5. $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.

---

1. Ključ: B; ni v 3NF

2. Ključ: BD; ni v 3NF

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

4. Ključ: A, ni v 3NF

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

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.