DB->normalizer

Tutorial

Algorithmen

Normalformen

1NF

Schema ist in 1NF, wenn alle Attribute atomar sind (trivial).

2NF

Schema ist in 2NF, wenn es in 1NF ist und für jedes Attribut b auf der rechten Seite gilt:

b ist Teil eines Kandidatenschlüssels oder
b ist nicht von einer echten Teilmenge eines Kandidatenschlüssels abhängig

3NF

Schema ist in 3NF, wenn jede FD α->β mindestens eine der folgenden Bedingungen erfüllt:

α->β ist trivial (β⊆α)
α ist Superschlüssel
Jedes Attribut in β ist in einem Kandidatenschlüssel enthalten

BCNF

Schema ist in BCNF, wenn jede FD α->β mindestens eine der folgenden Bedingungen erfüllt:

α->β ist trivial (β⊆α)
α ist Superschlüssel

4NF

Schema ist in 4NF, wenn jede MVD α->>β mindestens eine der folgenden Bedingungen erfüllt:

α->>β ist trivial (β⊆α oder α∪β = R)
α ist Superschlüssel

Kanonische Überdeckung

1 Linksreduktion

Was kann ich links weglassen?

2 Rechtsreduktion

Was kann ich rechts weglassen?

3 α→∅ entfernen

FDs mit leerer rechter Seite entfernen

4 FDs zusammenfassen

FDs mit gleichen linken Seiten zusammenfassen

Synthesealgorithmus (überführt R in 3NF)

1 Kanonische Überdeckung

Bestimme die kanonische Überdeckung (s. oben)

2 Relationsschemata formen

Aus jeder FD der kanonischen Überdeckung entsteht eine neue Relation

3 Schlüssel hinzufügen

Füge ein neues Relationsschema mit einem Kandidatenschlüssel hinzu, falls keiner der Kandidatenschlüssel vollständig in einem Schema enthalten ist

4 Redundante Schemata eliminieren

Eliminiere R_a, wenn R_a ⊆ R_a'

Dekompositionsalgorithmus (überführt R in BCNF)

Initialisierung

Starte mit Z={R}

Solange es noch eine FD in einem Schema R_i ∈ Z gibt, die die BCNF verletzt

Zerlege R_i in
- R_i1 = α ∪ β
- R_i2 = R_i - β
Entferne R_i aus Z und füge R_i1 und R_i2 ein

Dekompositionsalgorithmus (überführt R in 4NF)

Initialisierung

Starte mit Z={R}

Solange es noch eine MVD in einem Schema R_i ∈ Z gibt, die die 4NF verletzt

Zerlege R_i in
- R_i1 = α ∪ β
- R_i2 = R_i - β
Entferne R_i aus Z und füge R_i1 und R_i2 ein

DB->normalizer

Relation eingeben

FDs/MVDs eingeben

Neues Schema generieren

Algorithmen

Normalformen

1NF

2NF

3NF

BCNF

4NF

Kanonische Überdeckung

1 Linksreduktion

2 Rechtsreduktion

3 α→∅ entfernen

4 FDs zusammenfassen

Synthesealgorithmus (überführt R in 3NF)

1 Kanonische Überdeckung

2 Relationsschemata formen

3 Schlüssel hinzufügen

4 Redundante Schemata eliminieren

Dekompositionsalgorithmus (überführt R in BCNF)

Initialisierung

Solange es noch eine FD in einem Schema R_i ∈ Z gibt, die die BCNF verletzt

Dekompositionsalgorithmus (überführt R in 4NF)

Initialisierung

Solange es noch eine MVD in einem Schema R_i ∈ Z gibt, die die 4NF verletzt

DB->normalizer

Relation eingeben

FDs/MVDs eingeben

Neues Schema generieren

Algorithmen

Normalformen

1NF

2NF

3NF

BCNF

4NF

Kanonische Überdeckung

1 Linksreduktion

2 Rechtsreduktion

3 α→∅ entfernen

4 FDs zusammenfassen

Synthesealgorithmus (überführt R in 3NF)

1 Kanonische Überdeckung

2 Relationsschemata formen

3 Schlüssel hinzufügen

4 Redundante Schemata eliminieren

Dekompositionsalgorithmus (überführt R in BCNF)

Initialisierung

Solange es noch eine FD in einem Schema Ri ∈ Z gibt, die die BCNF verletzt

Dekompositionsalgorithmus (überführt R in 4NF)

Initialisierung

Solange es noch eine MVD in einem Schema Ri ∈ Z gibt, die die 4NF verletzt

Solange es noch eine FD in einem Schema R_i ∈ Z gibt, die die BCNF verletzt

Solange es noch eine MVD in einem Schema R_i ∈ Z gibt, die die 4NF verletzt