prev up next

Bestimmung funktionaler Abhängigkeiten

Wir betrachten folgendes Relationenschema:

ProfessorenAdr : {[PersNr, Name, Rang, Raum,
  Ort, Straße, PLZ, Vorwahl, BLand, Landesregierung]}

Hierbei sei Ort der eindeutige Erstwohnsitz des Professors, die Landesregierung sei die eindeutige Partei des Ministerpräsidenten, BLand sei der Name des Bundeslandes, eine Postleitzahl ( PLZ) ändere sich nicht innerhalb einer Straße, Städte und Straßen gehen nicht über Bundesgrenzen hinweg.

Folgende Abhängigkeiten gelten:

1. {PersNr} $ \rightarrow$ {PersNr, Name, Rang, Raum,
      Ort, Straße, PLZ, Vorwahl, BLand, EW, Landesregierung}
2. {Ort, BLand} $ \rightarrow$ {Vorwahl}
3. {PLZ} $ \rightarrow$ {BLand, Ort}
4. {Ort, BLand, Straße} $ \rightarrow$ {PLZ}
5. {BLand} $ \rightarrow$ {Landesregierung}
6. {Raum} $ \rightarrow$ {PersNr}

Hieraus können weitere Abhängigkeiten abgeleitet werden:

7. {Raum} $ \rightarrow$ {PersNr, Name, Rang, Raum,
      Ort, Straße, PLZ, Vorwahl, BLand, Landesregierung}
8. {PLZ} $ \rightarrow$ {Landesregierung}

Bei einer gegebenen Menge F von funktionalen Abhängigkeiten über der Attributmenge U interessiert uns die Menge F+ aller aus F ableitbaren funktionalen Abhängigkeiten, auch genannt die Hülle (engl. closure) von F.

Zur Bestimmung der Hülle reichen folgende Inferenzregeln, genannt Armstrong Axiome, aus:

Die Armstrong-Axiome sind sound (korrekt) und complete (vollständig). Korrekt bedeutet, daß nur solche FDs abgeleitet werden, die von jeder Ausprägung erfüllt sind, für die F erfüllt ist. Vollständig bedeutet, daß sich alle Abhängigkeiten ableiten lassen, die durch F logisch impliziert werden.

Weitere Axiome lassen sich ableiten:

Wir wollen zeigen: { PLZ} $ \rightarrow$ { Landesregierung} läßt sich aus den FDs 1-6 für das Relationenschema ProfessorenAdr herleiten:

Oft ist man an der Menge von Attributen $ \alpha^{+}_{}$ interessiert, die von $ \alpha$ gemäß der Menge F von FDs funktional bestimmt werden:

$\displaystyle \alpha^{+}_{}$ : = {$\displaystyle \beta$ $\displaystyle \subseteq$ U | $\displaystyle \alpha$ $\displaystyle \rightarrow$ $\displaystyle \beta$ $\displaystyle \in$ F+}

Es gilt der Satz:

$ \alpha$ $ \rightarrow$ $ \beta$ folgt aus Armstrongaxiomen genau dann wenn $ \beta$ $ \alpha^{+}_{}$.

Die Menge $ \alpha^{+}_{}$ kann aus einer Menge F von FDs und einer Menge von Attributen $ \alpha$ wie folgt bestimmt werden:

X0 : = $\displaystyle \alpha$

Xi + 1 : = Xi $\displaystyle \cup$ $\displaystyle \gamma$  falls $\displaystyle \beta$ $\displaystyle \rightarrow$ $\displaystyle \gamma$ $\displaystyle \in$ F$\displaystyle \land$$\displaystyle \beta$ $\displaystyle \subseteq$ Xi

D. h. von einer Abhängigkeit $ \beta$ $ \rightarrow$ $ \gamma$, deren linke Seite schon in der Lösungsmenge enthalten ist, wird die rechte Seite hinzugefügt. Der Algorithmus wird beendet, wenn keine Veränderung mehr zu erzielen ist, d. h. wenn gilt: Xi + 1 = Xi.

Beispiel
:

Sei U = { A, B, C, D, E, G}
Sei F = { AB $ \rightarrow$ C, C $ \rightarrow$ A, BC $ \rightarrow$ D, ACD $ \rightarrow$ B,
      D $ \rightarrow$ EG, BE $ \rightarrow$ C, CG $ \rightarrow$ BD, CE $ \rightarrow$ AG}
Sei X = {B, D}
  X0 = BD
  X1 = BDEG
  X2 = BCDEG
  X3 = ABCDEG = X4, Abbruch.
Also: (BD)+ = ABCDEG

Zwei Mengen F und G von funktionalen Abhängigkeiten heißen genau dann äquivalent (in Zeichen F G), wenn ihre Hüllen gleich sind:

F $\displaystyle \equiv$ G $\displaystyle \Leftrightarrow$ F+ = G+

Zum Testen, ob F+ = G+, muß für jede Abhängigkeit $ \alpha$ $ \rightarrow$ $ \beta$ F überprüft werden, ob gilt: $ \alpha$ $ \rightarrow$ $ \beta$ G+, d. h. $ \beta$ $ \subseteq$ $ \alpha^{+}_{}$. Analog muß für die Abhängigkeiten $ \gamma$ $ \rightarrow$ $ \delta$ G verfahren werden.

Zu einer gegebenen Menge F von FDs interessiert oft eine kleinstmögliche äquivalente Menge von FDs.

Eine Menge von funktionalen Abhängigkeiten heißt minimal $ \Leftrightarrow$

  1. Jede rechte Seite hat nur ein Attribut.
  2. Weglassen einer Abhängigkeit aus F verändert F+.
  3. Weglassen eines Attributs in der linken Seite verändert F+.
Konstruktion der minimalen Abhängigkeitsmenge geschieht durch Aufsplitten der rechten Seiten und durch probeweises Entfernen von Regeln bzw. von Attributen auf der linken Seite.

Beispiel
:

Sei U = { A, B, C, D, E, G}
Sei F = { AB $ \rightarrow$ C, D $ \rightarrow$ EG
      C $ \rightarrow$ A, BE $ \rightarrow$ C,
      BC $ \rightarrow$ D, CG $ \rightarrow$ BD,
      ACD $ \rightarrow$ B, CE $ \rightarrow$ AG }

Aufspalten der rechten Seiten liefert

AB $ \rightarrow$ C
C $ \rightarrow$ A
BC $ \rightarrow$ D
ACD $ \rightarrow$ B
D $ \rightarrow$ E
D $ \rightarrow$ G
BE $ \rightarrow$ C
CG $ \rightarrow$ B
CG $ \rightarrow$ D
CE $ \rightarrow$ A
CE $ \rightarrow$ G
Regel CE $ \rightarrow$ A ist redundant wegen C $ \rightarrow$ A
  CG $ \rightarrow$ B ist redundant wegen CG $ \rightarrow$ D
      C $ \rightarrow$ A
      ACD $ \rightarrow$ B
Regel ACD $ \rightarrow$ B kann gekürzt werden zu CD $ \rightarrow$ B, wegen C $ \rightarrow$ A

prev up next