12.1 Das Defizit

Obwohl die BCNF zu weitgehend redundanzfreien Relationen führt, fanden sich im Laufe der Zeit doch Attributkonstellationen, die von ihr nicht erfasst werden. Eine solche wird in der 4NF bearbeitet.

Oft ist zu hören, dass diese Normalform keine Bedeutung in der Praxis hätte. Dies ist nicht ganz richtig. Sie gibt uns zumindest einen Hinweis auf eine mögliche Fehlerquelle gleich zu Beginn der Normalisierung, bei der Behandlung der unnormalisierten Relation. Deshalb soll sie hier auch betrachtet werden.

Der Hintergrund der vierten Normalform kann wie folgt beschrieben werden: Angenommen, es liegt eine unnormalisierte Relation vor, in der drei oder mehr Attribute Mehrfacheinträge aufweisen (d.h., sie sind nicht flach; Einige Autoren verwenden auch den Begriff Wiederholungsgruppen, vom angelsächsischen repeating groups). In einem solchen Fall könnte man auf die Idee kommen, diese Mehrfacheinträge einfach durch Tupelvermehrung gegeneinander aufzulösen. Dabei entsteht aber eine Relation mit Strukturdefiziten, die von den bisherigen Normalformen nicht erfasst werden. Dazu ein Beispiel.

Problemursache: mehrfache Mehrfacheinträge

12.2 Beispiel Vorlesungsbetrieb

Gegeben sei die folgende unnormalisierte Relation, mit der die Beziehungen zwischen Vorlesungen (als solchen, also nicht Vorlesungstermine), den Dozenten und Räumen in einer Tabelle erfasst werden. Es gilt folgende Semantik: Eine Vorlesung kann von mehreren Dozenten gehalten werden und sie kann in mehreren Räumen stattfinden (nur in bestimmten, wegen ihrere Anforderungen: Größe, DV-Ausstattung, ...).

Was bedeuten in einer solchen Relation die Tupel (Zeilen)? Die Bedeutung der ersten Zeile ist wie folgt: Vorlesung V1 wird von den Dozenten D1 und D2 angeboten und kann in den Räumen R1 und R2 durchgeführt werden. Entsprechend bedeutet die zweite Zeile: Vorlesung V2 wird von D1 angeboten und kann in R2 stattfinden. Und die dritte: Vorlesung V3 wird von D1 und D3 angeboten und kann in R3 stattfinden.

Wird diese unnormalisierte Tabelle nun direkt mittels Tupelvermehrung in die 1NF gebracht, müssen die Mehrfacheinträge miteinander kombiniert werden (mittels des kartesischen Produkts), nur dann bleibt die Information der unnormalisierten Relation erhalten. Dann entsteht folgende Relation:

Normalisierung durch kartesisches Produkt

In dieser haben die Tupel folgende Bedeutung:

• Tupel 1: V1 wird von D1 angeboten und kann in R1 stattfinden
• Tupel 2: V1 wird von D1 angeboten und kann in R2 stattfinden
• Tupel 3: V1 wird von D2 angeboten und kann in R1 stattfinden
• Tupel 4: V1 wird von D2 angeboten und kann in R2 stattfinden

usw. Die ersten vier Tupel werden benötigt, um den Informationsgehalt des ersten Tupels der Relation V-D-R_UN zu erfassen (1 * 2 * 2 = 4). Es ist leicht zu sehen, dass eine solche Relation nur Schwierigkeiten bereitet. Trotzdem ist sie in BCNF, da alle Attribute Schlüsselattribute sind ("all key") und die Regeln der BCNF gegenüber einer solchen Situation nicht greifen.

Die Redundanz ist offensichtlich: Dass V1 von D1 angeboten wird, ist nicht nur einmal erfasst, sondern mehrmals (für jeden Raum). Ebenso wird die Tatsache, dass V1 in R1 stattfinden kann, mehrfach erfasst (Zahl der Dozenten). Dieses Strukturdefizit entsteht, weil im Rahmen der Normalisierung die Information auf "flache" Tupel verteilt werden muss. Die Komplexität entsteht durch die Bildung der Relation aus dem kartesischen Produkt der Ausprägungen mit Mehrfacheinträgen. Dadurch "lastet" auf ihr eine komplexe Regel:

Redundanz

Falls (V1, D1, R1) und (V1, D2, R2) beide da sind, müssen auch (V1, D1, R2) und (V1, D2, R1) vorkommen.

Dies resultiert aus der Entstehung der Relation durch Tupelvermehrung. Aus dem ersten Teil der Regel folgt, dass in der unnormalisierten Ursprungsrelation die nachfolgend aufgeführte Zeile vorhanden war:

Denn diese führt zu folgenden Kombinationen:

War diese aber vorhanden, müssen (wegen der Bildung des kartesischen Produkts aus (D1, D2) x (R1, R2) auch die Tupel (V1, D2, R1) und (V1, D2, R2) vorhanden sein. Eine solch komplexe Regel (eine semantische Integritätsbedingung) kann im Zeitverlauf kaum aufrechterhalten werden. Bei jedem neuen Eintrag, der entweder mehrere Hosts oder mehrere Produzenten aufweist muss ja nicht nur ein Tupel, sondern es müssen mehrere eingetragen werden.

Wird zum Beispiel V1 zusätzlich von einem Dozenten D4 angeboten, muss nicht nur das Tupel (V1, D4, R1), sondern auch das Tupel (V1, D4, R3) zusätzlich eingetragen werden.

Auch hier besteht die Lösung wiederum in einer Zerlegung der Relation. Mit den obigen Abkürzungen wird V-D-RS in die zwei Relationen

Normalisierung durch Zerlegung

V-D_4NF (#(Vorlesung, Dozent))

V-D ist auch gleich in 5NF

und

V-R_4NF (#(Vorlesung, Raum))

V-R ebenfalls

zerlegt. V-D_4NF erfasst nun die Beziehung zwischen Vorlesungen und ihren Dozenten ("welcher Dozent gibt welche Vorlesung). V-R_4NF erfasst die Beziehung zwischen Vorlesungen und Räumen ("in welchen Räumen können die Vorlesungen stattfinden). Es entstehen die folgenden Tabellen:

Die durchgestrichenen Zeilen zeigen wiederum die Redundanz der ursprünglichen Relation. Die Kennzeichnung von Vorlesung als Fremdschlüssel (durch Unterstreichung) hat nicht genau dieselbe Bedeutung wie sonst, da (hier) ja die Relation fehlt, die Vorlesungen beschreibt und in der das Attribut Vorlesung Schlüssel wäre. Sie wurde trotzdem gewählt, weil die beiden Attribute Fremdschlüsselcharakter haben. Allerdings wäre eine direkte Verknüpfung problematisch (wegen der jeweils mehrfachen Ausprägungen), weshalb im folgenden Datenmodell eine Relation VORLESUNGEN ergänzt wurde.

Bewältigte Redundanz

Wegen der hier diskutierten Probleme mit mehrfachen Wiederholungsgruppen weist Date darauf hin, dass bei der Normalisierung einer unnormalisierten Relation auf jeden Fall zuerst die voneinander unabhängigen Wiederholungsgruppen getrennt werden sollten [Date 1990, S. 383].

Regel

12.3 Mehrwertige Abhängigkeit

Für die Definition der vierten Normalform (4NF), in der also die oben beschrieben Strukturdefizite nicht (mehr) auftreten, kann eine weitere Form der Abhängigkeit zwischen den Attributen einer Relation eingeführt werden, die sog. mehrwertige Abhängigkeit (MWA; engl. multi-valued-dependency (MVD)). Bei dieser stehen zwei Attribute A und B einer Relation in folgender Beziehung zueinander: Kennt man eine Ausprägung von A, kann man zwar nicht genau eine (einzige) von B "vorhersagen" (dies wäre eine funktionale Abhängigkeit), aber eine genau definierte Menge von Ausprägungen von B. Beispiele hierfür sind leicht zu finden.

In obiger Relation zu Vorlesungen - Dozenten - Räumen:

• Kennt man die Bezeichnung einer Vorlesung, kann man zwar nicht genau einen Dozenten nennen, der sie halten kann, aber eine genau definierte Gruppe von Dozenten.
• Kennt man die Bezeichnung einer Vorlesung, kann man zwar nicht genau einen Raum nennen, der geeignet ist, aber eine genau definierte Menge von Räumen, in denen die Vorlesung stattfinden kann.

In einer Relation zu den Angestellten eines Unternehmens:

• Vom Namen eines Angestellten kann nicht eine einzelne von ihm beherrschte Programmiersprache genannt werden, aber eine Liste, nämlich genau die der von ihm beherrschten.

In einer Relation zu Datenbanksystemen:

• Da ein DBS mehrere Datentypen hat, gilt auch hier eine solche Beziehung, da vom Namen eines Datenbanksystems zwar nicht auf einen Datentyp, aber auf eine wohldefinierte Menge von Datentypen geschlossen werden kann.

Aus der Sicht der Abhängigkeiten zwischen Attributen bedeutet dies, dass nicht eine Ausprägung genannt werden kann, aber eine genau definierte Menge. Das ist die oben angeführte mehrwertige Abhängigkeit (MWA).

Exkurs: Abhängigkeiten zwischen den Attributen einer Relation

Attribute einer Relation stehen miteinander in Beziehung. Mit der obigen mehrwertigen Abhängigkeit sind insgesamt folgende Beziehungen möglich:

• Unabhängigkeit (die Ausprägungen der beiden Attribute sind unabhängig voneinander. Jede Ausprägung beschreibt eine eigenständige Eigenschaft).

• volle und einfache funktionale Abhängigkeit

• transitive Abhängigkeit

• mehrwertige Abhängigkeit

Mit Ausnahme der ersten gibt jede Beziehung einen Hinweis auf Optimierungsbedarf.

In einer Relation schlägt sich die mehrwertige Abhängigkeit in der Form von Mehrfacheinträgen bei einem der Attribute nieder. Diese Form der Abhängigkeit zwischen zwei Attributen einer Relation ist somit etwas weiter als die der funktionalen Abhängigkeit, aber deutlich enger als die der Unabhängigkeit zweier Attribute (dann ist überhaupt keine "Vorhersage" möglich ist).

"Wieviel Vorhersage" ist möglich

Schwierigkeiten bereitet diese Art der Abhängigkeit nur, falls sie doppelt in einer unnormalisierten Relation vorkommt. Dann müssen mindestens drei Attribute A, B und C im Spiel sein und zwei davon stehen in der beschriebenen Abhängigkeit vom dritten (wie im obigen Beispiel).

Seien A, B, C Attribute einer Relation R. B heißt mehrwertig abhängig von A, in Zeichen: A_C =>=> B falls für jede Kombination von Attributs­aus­prä­gungen von A, C eine wohldefinierte Menge von Ausprägungen von B existiert, die von A, aber nicht von C abhängt.

Definition: Mehrwertige Abhängigkeit (MWA)

Es gilt dann auch: A_B =>=> C

Am leichtesten veranschaulicht man sich die Definition anhand des obigen Beispiels. Hier gilt

VorlesungDozent =>=> Raum

VorlesungRaum =>=> Dozent

Das tiefgestellte Attribut wird mit angegeben, um deutlich zu machen, dass die MWA nur dann gegeben ist, wenn drei Attribute im Spiel sind, denn nur dann treten die beschriebenen Schwierigkeiten auf. Liegen nur zwei (die zwei mit den Mehrfacheinträgen) vor, werden sie gegeneinander aufgelöst und es entsteht eine Situation wie bei einer Verbindungsrelation.

Jede funktionale Abhängigkeit ist auch eine (einfache) mehrwertige Abhängigkeit (eine, bei der nur ein "Treffer" vorliegt). Im Folgenden sollen mehrwertige Abhängigkeiten, die keine funktionalen Abhängigkeiten sind, als echte mehrwertige Abhängigkeiten bezeichnet werden.

Echte MWA

12.4 Definition 4NF

Eine Relation mit einer echten mehrwertigen Abhängigkeit hat die beschriebenen Strukturdefizite, die durch einen weiteren Normalisierungsschritt beseitigt werden, der zur vierten Normalform (4NF) führt. Dies geschieht so, dass aus jedem Attribut mit Mehrfacheinträgen zusammen mit dem Schlüssel eine neue Relation gebildet wird: Waren A, B und C die Attribute mit A_C =>=> B und A_B =>=> C, dann kann die Relation in die zwei Relationen R1(A,B) und R2(A,C) zerlegt werden. Die so entstehenden Relationen befinden sich dann in vierter Normalform.

Eine Relation R ist in 4NF, falls sie in BCNF ist und falls sie keine echten mehrwertigen Abhängigkeiten aufweist.

Definition 1: 4NF

Gleichwertig ist die folgende Definition nach [Date 1990, S. 558]:

Eine Relation R ist in 4NF, falls alle mehrwertigen Abhängigkeiten in R auf den Schlüsseln von R basieren.

Definition 2: 4NF

Denn wenn sie auf den Schlüsseln beruhen, liegt bei einem Schlüssel aus einem Attribut in einer Richtung immer Eindeutigkeit vor, vom Schlüssel zu den Nichtschlüsselattributen. Sollten - Alternative 2 - zwei Attribute mit Mehrfacheinträgen als Schlüssel vorliegen, sind sie von allen anderen unabhängig, werden gegeneinander aufgelöst und stellen einen zusammengesetzten Schlüssel dar.

Wie oben ausgeführt, treten die Probleme nur auf, wenn zwei Attribute mit Mehrfacheinträgen auftreten. Liegt nur ein solches vor, wird die Tabelle einfach flach gemacht, z.B. durch Tupelvermehrung (vgl. oben).

Faustregel

Probleme mit der 4NF können also nur auftreten, wenn eine echte mehrwertige Abhängigkeit durch Tupelvermehrung aufgelöst wurde. Umgekehrt: Liegt keine echte MWA vor, können die Strukturdefizite, die zu Problemen mit der 4NF führen, nicht vorliegen.