Normalformen

BCNF⊆\subseteq3NF⊆\subseteq2NF⊆\subseteq1NF

Zerlegung

Es entstehen Anomalien, wenn wir nicht Entities und Relations getrennt speichern.

Deshalb braucht man sinnvolle Zerlegung.

Zerlegung vonR\mathcal RinR1,…,Rn\mathcal{R}_{1}, \ldots, \mathcal{R}_{n}

att⁡(R1)∪⋯∪att⁡(Rn)=att⁡(R) \small \operatorname{att}\left(\mathcal{R}_{1}\right) \cup \cdots \cup \operatorname{att}\left(\mathcal{R}_{n}\right)=\operatorname{att}(\mathcal{R}) 

Kriterien: Verlustlosigkeit und Abhängigkeitstreue

Verlustlostigkeit

Die Informationen in R\mathcal R müssen nach der Zerlegung rekonstruierbar sein.

R=πR1(R)⋈πR2(R)⋈⋯⋈πRn(R) \small R=\pi_{\mathcal{R}_{1}}(R) \bowtie \pi_{\mathcal{R}_{2}}(R) \bowtie \cdots \bowtie \pi_{\mathcal{R}_{n}}(R) 

Die Join-Attribute müssen Super-Schlüssel sein.

Abhängigkeitstreue

Die FDs in R\mathcal R müssen nach der Zerlegung übertragbar sein.

Sei

R′⊆R\small \mathcal{R}^{\prime} \subseteq \mathcal{R}

F[R′]={α→β∈F∣α∪β⊆R′} \small F\left[\mathcal{R}^{\prime}\right]=\left\{\alpha \rightarrow \beta \in F \mid \alpha \cup \beta \subseteq \mathcal{R}^{\prime}\right\} 

Es muss gelten

F≡(F+[R1]∪⋯∪F+[Rn]) \small F \equiv\left(F^{+}\left[\mathcal{R}_{1}\right] \cup \cdots \cup F^{+}\left[\mathcal{R}_{n}\right]\right)  bzw

F+=(F+[R1]∪⋯∪F+[Rn])+ \small F^{+}=\left(F^{+}\left[\mathcal{R}_{1}\right] \cup \cdots \cup F^{+}\left[\mathcal{R}_{n}\right]\right)^{+} 

3. Normalform

Geschichte

1NF: 1. Normalform

Wenn Domänen von R\mathcal R atomar sind (keine nested tables)

2NF: 2. Normalform

Wenn nur genau ein einziges Konzept modeliert wird

Definition 3NF

α⊆R\alpha \subseteq \mathcal{R} , B∈RB\in \mathcal R

Wir wandeln alle FDs so um dass rechts nur eine Attribute steht.

∀(α→B)∈F:\forall (\alpha \rarr B) \in F: muss mindestens eines der Bedingungen gelten:

B∈αB\in \alpha (triviale FD)

α\alpha ist ein Superschlüssel von R\mathcal R

Attribut BB ist Teil des Schlüssel von R\mathcal R

Synthese-Algorithmus

Ermöglicht Zerlegung in 3NF

R=R1∪⋯∪Rn \mathcal{R}=\mathcal{R}_{1} \cup \cdots \cup \mathcal{R}_{n} 

Verlustlos, Abhängigkeitstreu und alle Ri\mathcal R_i sind in 3NF.

Synthese-Algorithmus

  1. Bestimme kanonische Überdeckung FCF_C zu FF

    Damit wir nur so viel zerlegen wie unbedingt notwendig

  1. ∀(α→β)∈FC:\forall (\alpha \rarr \beta) \in F_C:

    Erstelle für jede FD ein eigenes Relationenschema Ri:=α∪β\mathcal{R}_{i}:=\alpha \cup \beta

    Ordne jeder Ri\mathcal R_i die FDs Fi:=Fc[Ri]F_{i}:=F_{c}\left[\mathcal{R}_{i}\right] zu

    FC[Ri]={α→β∈FC∣α∪β⊆Ri} \small F_C[\mathcal{R}_i]=\left\{\alpha \rightarrow \beta \in F_C \mid \alpha \cup \beta \subseteq \mathcal{R}_i\right\} 

    Damit Abhängigkeitstreue erfüllt ist

  1. Falls keines der erzeugten Teilschemata einen Schlüssel von R\mathcal R enthält,
    1. wähle einen Schlüssel κ∈R\kappa \in \mathcal{R}

      Keinjoinmöglich, deshalb IDs erzeugen

    1. Definiere zusätzlich das Schema Rκ:=κ\mathcal{R}_{\kappa}:=\kappa wobei Fκ:=∅F_\kappa:=\empty
  1. Kürze überflüssige Schemata wenn sie in einem anderen enthalten sind.

Boyce-Codd Normalform

Es werden mit 3NF nicht alle Anomalien beseitigt.

Nur in BCNF wird Anomalie-Freiheit garantiert.

Definition BCNF

α⊆R\alpha \subseteq \mathcal{R} , B∈RB\in \mathcal R

Wir wandeln alle FDs so um dass links nur eine Attribute steht.

∀(α→B)∈F:\forall (\alpha \rarr B) \in F: muss mindestens eines der Bedingungen gelten:

B∈αB\in \alpha (triviale FD)

α\alpha ist ein Superschlüssel von R\mathcal R

AttributB∈\sout{B\in}einem der Schlüssel vonR\sout{\mathcal R}

Dekompositions-Algorithmus

Ermöglicht Zerlegung in BCNF

R=R1∪⋯∪Rn \mathcal{R}=\mathcal{R}_{1} \cup \cdots \cup \mathcal{R}_{n} 

Verlustlos, Abhängigkeitstreu und alle Ri\mathcal R_i sind in 3NF.

Es ist nicht immer möglich, dass Zerlegung Abhängigkeitstreu ist.

Dekompositions-Algorithmus

  1. Z={(R,F)}\small Z=\{(\mathcal{R}, F)\}
  1. ∀(Ri,Fi)∈Z\small \forall(\mathcal{R}_i, F_i) \in Z :

    Wenn nicht in BCNF, dann wähle die (α→β)∈Fi\small (\alpha \rarr \beta) \in F_i welche die Bedingung verletzt

    1. Zerlege Ri\small \mathcal{R}_i

      Ri1:=(α∪β)Fi1:=Fi+[Ri1] \small \mathcal{R}_{i_{1}}:=(\alpha \cup \beta)\quad \quad \quad ~~F_{i_{1}}:=F_{i}^{+}\left[\mathcal{R}_{i_{1}}\right] 

      Ri2:=Ri−(β−α)Fi2:=Fi+[Ri2] \small \mathcal{R}_{i_{2}}:=\mathcal{R}_{i}-(\beta-\alpha) \quad F_{i_{2}}:=F_{i}^{+}\left[\mathcal{R}_{i_{2}}\right] 

      wobeiFi+[Ri]={α→β∈Fi+∣α∪β⊆Ri} \small F_i^+[\mathcal{R}_i]=\left\{\alpha \rightarrow \beta \in F_i^+ \mid \alpha \cup \beta \subseteq \mathcal{R}_i\right\} 

    1. Entferne (Ri,Fi)\small (\mathcal{R}_i, F_i) aus Z\small Z
    1. Füge (Ri1,Fi1) \small \left(\mathcal{R}_{i_{1}}, F_{i_{1}}\right)  und (Ri2,Fi2) \small \left(\mathcal{R}_{i_{2}}, F_{i_{2}}\right)  in ZZ ein

      Z:=(Z−({Ri,Fi)})∪{(Ri1,Fi1)}∪{(Ri2,Fi2)} \small Z:=\left(Z-\left(\left\{\mathcal{R}_{i}, F_{i}\right)\right\}\right) \cup\left\{\left(\mathcal{R}_{i_{1}}, F_{i_{1}}\right)\right\} \cup\left\{\left(\mathcal{R}_{i_{2}}, F_{i_{2}}\right)\right\}