Osnove podatkovnih baz - vaje 1.4.2021

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 \lbrace A \rbrace \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?

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?

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.

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.