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

\(R\) je v 3NF, ni v BCNF.

Primer podatkov:

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:

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.

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

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

2. 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.

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

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

2. Ključ: BD; ni v 3NF

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

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

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

4. Ključ: A, ni v 3NF

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

5. 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)"]