Skip to content

2020-04-02.md

Latest commit

 

History

History
250 lines (176 loc) · 5.31 KB

2020-04-02.md

File metadata and controls

250 lines (176 loc) · 5.31 KB
tags vaje, opb, normalizacija
hackmd https://hackmd.io/lM4y6e9DRSi_w-gcOpsl_g
plugins mathjax, mermaid

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)"]
Loading

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
Loading

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)"]
    Loading

  2. Ključ: AB

    graph LR

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

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)"]
    Loading

  2. Ključ: BD; ni v 3NF

    graph LR

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

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

    graph LR

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

  4. Ključ: A, ni v 3NF

    graph LR

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

  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)"]
    Loading