Synthesealgorithmus-Normalform

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Synthesealgorithmus-Normalform beschreibt, wie aus einem Datenbankentwurf ein Relationenschema der 3. Normalform wird. Ein alternativer Algorithmus ist der Zerlegungsalgorithmus, welcher in die BCNF transferiert. Dabei können allerdings Abhängigkeiten verloren gehen.

[Bearbeiten] Voraussetzung

Es müssen alle funktionalen Abhängigkeiten unter den Attributen bekannt sein.

Beispiel:

Relation(A,B,C,D,E)
A -> B,C
A,D -> B
B,D -> E
A,D -> E

[Bearbeiten] Reduktion

Dies wird auch die Berechnung der kanonischen Überdeckung genannt.

[Bearbeiten] 1.Schritt: Linksreduktion

Für alle $\psi \in \Psi$ ersetze $\Psi \rightarrow \Gamma$ durch $\Psi \setminus \{\psi\} \rightarrow \Gamma$ , falls $Γ$ schon durch $\Psi \setminus \{\psi\} \rightarrow \Gamma$ determiniert ist.

[Bearbeiten] 2.Schritt: Rechtsreduktion

Für alle $\gamma \in \Gamma$ ersetze $\Psi \rightarrow \Gamma$ durch $\Psi \rightarrow \Gamma \setminus\{\gamma\}$ , falls $γ$ schon transitiv durch $Ψ$ bestimmt ist.

[Bearbeiten] 3.Schritt: Leere Klauseln

Eliminiere Klauseln der Form $\Psi \rightarrow \varnothing$

[Bearbeiten] 4.Schritt: Zusammenfassen

Fasse Formeln $a \rightarrow b_0 , a \rightarrow b_1 ...$ zu $a \rightarrow b_0 \cup b_1 ...$ zusammen.

[Bearbeiten] Beispiel

Erster und zweiter Schritt:

Relation(A,B,C,D,E)
{A} -> {B,C} # bleibt
{A} -> {B} # D fällt weg (Linksreduktion) (1)
{B,D} -> {E} # bleibt
{A,D} -> {} # E fällt weg (Rechtsreduktion)

Dritter und vierter Schritt:

Relation(A,B,C,D,E)
{A} -> {B,C} # (1) ist hier enthalten
{B,D} -> {E}

[Bearbeiten] Neues Relationenschema

Aus allen Ψ -> Γ wird R(Ψ, Γ).

Zusätzlich muss ein neuer Schlüssel gefunden werden. Gegebenenfalls muss eine neue Relation erzeugt werden. Überflüssige Relationen können gestrichen werden.

Beispiel:

Relation(A,B,C) # A ist Primärschlüssel
Relation(B,D,E) # B ist Primärschlüssel
Relation(A,B) # A,B sind Primärschlüssel

[Bearbeiten] Formaler Algorithmus

Eingabe: universelles Schema R=(U,F) Ausgabe: 3. Normalform D von R

B:=Reduktion(F) R:={} i:=0 for each Y $\subset$ U mit $(\exist A \in U):Y\rightarrow A \in B$

 i:=i+1
 
  $R i : = (X i,π X i 1 (B))$

if $(\forall R_i\in R): X_i \rightarrow X_i\rightarrow U\notin B^+$

 i:=i+1

D:=(R,{})

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung.

Von „http://de.wikipedia.org../../../s/y/n/Synthesealgorithmus-Normalform_93aa.html“

Kategorien: Datenbankmodellierung | Wikipedia:Überarbeiten