Synthesealgorithmus

Algorithmus für relationale Datenbankschemata
(Weitergeleitet von Synthesealgorithmus-Normalform)

Der Synthesealgorithmus beschreibt, wie aus einem relationalen Datenbankschema ein Relationenschema der dritten Normalform wird. Das besondere an diesem Algorithmus ist, dass er im Gegensatz zu der intuitiven Zerlegung des Schemas in die dritte Normalform die Abhängigkeitserhaltung in jedem Fall garantiert.

Ein alternativer Algorithmus ist der Zerlegungsalgorithmus, welcher in die Boyce-Codd-Normalform (BCNF) transferiert. Dabei können allerdings Abhängigkeiten verloren gehen (nicht abhängigkeitstreu). Er ist insofern eine Alternative, als jedes relationale Schema, welches in BCNF transformiert wird, dann auch automatisch in dritter Normalform vorliegt.

Voraussetzung

Bearbeiten

Es müssen alle funktionalen Abhängigkeiten   der zu zerlegenden Relation   unter den Attributen bekannt sein.

Beispiel:

  •  
  •  

Der Synthesealgorithmus besteht dann aus vier Schritten:

  1. Reduktion von  , d. h. die Bestimmung der kanonischen Überdeckung.
  2. Erzeugen der neuen Relationenschemata aus der kanonischen Überdeckung.
  3. Ggf. die Hinzunahme einer Relation, die nur den Ursprungsschlüssel enthält.
  4. Elimination der Schemata, die in einem anderen Schema enthalten sind.

Reduktion

Bearbeiten

Dies wird auch die Berechnung der kanonischen Überdeckung genannt.

1. Schritt: Linksreduktion

Bearbeiten

Für alle   ersetze   durch   , falls   schon durch   determiniert ist.

Die obige Bedingung lässt sich testen, indem man überprüft, ob   ist,[1] wobei F die Menge der funktionalen Abhängigkeiten bezeichnet. Falls dies zutrifft, kann   aus   entfernt werden.

Beispiel:  

  •  
  •  
  •  
  •  
  •  

In der zweiten funktionalen Abhängigkeit fällt E weg, da sich B und D in der Attributhülle von A ( ) befinden. In der letzten funktionalen Abhängigkeit fällt C weg, wegen  . Man kann es auch so formulieren: E wird in   nicht benötigt, um   zu erreichen.

Lösung:

  •  
  •  
  •  
  •  
  •  

2. Schritt: Rechtsreduktion

Bearbeiten

Für alle   ersetze   durch  , falls   schon transitiv durch   bestimmt ist.

Die obige Bedingung lässt sich überprüfen, indem man für jedes   testet, ob   ist. Falls dies zutrifft, kann   aus   entfernt werden. Hierbei handelt es sich um ein iteratives Verfahren, d. h.   enthält in jedem Schritt die bereits in vorherigen Schritten aktualisierten Abhängigkeiten.

An obigem Beispiel:

  •  
  •  
  •  
  •  
  •  

In der ersten funktionalen Abhängigkeit fällt B weg, da  . In der vierten funktionalen Abhängigkeit fällt ebenfalls das B weg, wegen  .

  •  
  •  
  •  
  •  
  •  

3. Schritt: Leere Klauseln

Bearbeiten

Eliminiere Klauseln der Form  

Im Beispiel aus Schritt 2 gibt es keine Abhängigkeiten mit leerer rechter Seite. Also gibt es in diesem Fall hier nichts zu tun.

4. Schritt: Zusammenfassen

Bearbeiten

Fasse Formeln   zu   zusammen.

Im Beispiel fassen wir nun Ausdrücke mit gleicher linker Seite zusammen:

  •  
  •  
  •  

Neues Relationenschema

Bearbeiten

Aus allen   wird  .

Zusätzlich muss ein neuer Schlüssel gefunden werden. Gegebenenfalls muss eine neue Relation erzeugt werden. Überflüssige Relationen können gestrichen werden, wenn diese in anderen enthalten sind.

Am Beispiel:

  •   #   ist Primärschlüssel
  •   #   ist Primärschlüssel
  •   #   ist Primärschlüssel (Die Elemente dieser Relation sind zwar schon durch   und   gegeben, jedoch muss zur Abhängigkeitserhaltung diese weiterhin aufgeführt werden, es dürfte nur entfernt werden, wenn eine Relation vollends in einer anderen enthalten wäre. Dies ist jedoch nicht möglich, da diese Fälle vorher durch die Links- und Rechtsreduktion entfernt wurden.)

Hinzufügen einer Relation

Bearbeiten

Nun muss durch Hinzunahme einer Relation eine Beziehung zwischen  ,   und   hergestellt werden. Das wird durch eine Relation   ermöglicht, die nur den Ursprungsschlüssel   enthält (beachte, dass   ist). Wir erhalten ein Schema in der 3. Normalform wie folgt:

  •  
  •  
  •  
  •  , wobei   und   jeweils Fremdschlüssel darstellen und zusammengenommen den Primärschlüssel von   erzeugen.

Formaler Algorithmus

Bearbeiten

Eingabe: universelles Schema  
Ausgabe: 3. Normalform   von  

 
 
 
 
 
 
 
 
 
 
 
 

Einzelnachweise

Bearbeiten
  1. A. Kemper, A. Eickler: Datenbanksysteme, ISBN 3-486-57690-9.