Kanonische Überdeckung

Die kanonische Überdeckung ist ein Konzept aus der relationalen Entwurfstheorie, die sich mit dem Entwurf der Schemata relationaler Datenbanken befasst.

Am Anfang des Entwurfs eines relationalen Schemas steht die Informationsbedarfsanalyse. Sie liefert die Menge der benötigten Attribute und eine Menge F der funktionalen Abhängigkeiten zwischen diesen Attributen. Basierend auf diesen Abhängigkeiten werden Normalformen für die Schemata relationaler Datenbanken definiert, die als „Gütekriterium“ für ein solches Schema gesehen werden.

Im Allgemeinen gibt es zu einer Menge funktionaler Abhängigkeiten viele verschiedene äquivalente Mengen funktionaler Abhängigkeiten. Zwei Mengen funktionaler Abhängigkeiten F und G heißen genau dann äquivalent, in Zeichen $F\equiv G$ , wenn ihre Attributhüllen gleich sind, in Zeichen $F^{+}=G^{+}$ . Sind F und G äquivalent, so heißt F Überdeckung von G und umgekehrt.

Es gibt zu einer gegebenen Menge F von funktionalen Abhängigkeiten eine eindeutige Attributhülle $F^{+}$ , die aber in der Regel viele funktionale Abhängigkeiten beinhaltet, was sich bei einer späteren Implementierung des Schemas in einer relationalen Datenbank negativ auswirkt, da bei jeder Änderungsoperation im Rahmen einer Konsistenzprüfung die Einhaltung sämtlicher spezifizierter funktionaler Abhängigkeiten überprüft werden muss.

Deshalb ist man im Entwurfsprozess relationaler Schemata an der kleinstmöglichen Menge der äquivalenten funktionalen Abhängigkeiten interessiert, der kanonischen Überdeckung der gegebenen Menge funktionaler Abhängigkeiten. Eine kanonische Überdeckung beschreibt also die kleinste gültige Menge von funktionalen Abhängigkeiten für ein bestimmtes relationales Schema. Die Ableitung einer solchen kanonischen Überdeckung gewährleistet ein redundanzfreies relationales Schema.

Zu einer gegebenen Menge F von funktionalen Abhängigkeiten nennt man $F_{*}$ eine kanonische Überdeckung, wenn folgende drei Eigenschaften erfüllt sind:

$F_{*}\equiv F$ , das heißt $F_{*}^{+}=F^{+}$
In $F_{*}$ existieren keine funktionalen Abhängigkeiten $\alpha \rightarrow \beta$ , wobei $\alpha$ und $\beta$ Mengen überflüssiger Attribute enthalten; das heißt, es muss gelten:

(a) $\forall A\in {\mathbf \alpha }:(F_{*}-(\alpha \rightarrow \beta )\cup ((\alpha -A)\rightarrow \beta ))\not \equiv F_{*}$

(b) $\forall B\in {\mathbf \beta }:(F_{*}-(\alpha \rightarrow \beta )\cup (\alpha \rightarrow (\beta -B)))\not \equiv F_{*}$

Jede linke Seite einer funktionalen Abhängigkeit in $F_{*}$ ist einzigartig. Dies kann durch fortgesetzte Anwendung der Vereinigungsregel auf funktionale Abhängigkeiten der Art $\alpha \rightarrow \beta$ und $\alpha \rightarrow \gamma$ erreicht werden, so dass die beiden funktionalen Abhängigkeiten durch $\alpha \rightarrow \beta \gamma$ ersetzt werden.

Algorithmus

Um aus einer gegebenen Menge von funktionalen Abhängigkeiten eine (die kanonische Überdeckung ist nicht eindeutig) kanonische Überdeckung zu finden, kann man folgenden Algorithmus verwenden:

Linksreduktion
Rechtsreduktion
Alle funktionalen Abhängigkeiten $\alpha \rightarrow \beta$ aus mit gleichem $\alpha$ zusammenfassen: Wenn $\alpha \rightarrow \beta \in F,\alpha \rightarrow \gamma \in F$ , dann entferne diese beiden funktionalen Abhängigkeiten aus und füge $\alpha \rightarrow \beta \gamma$ zu hinzu.

Basierend auf einem Artikel in:

Wikipedia.de