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:

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

$$\rightarrow$$ 2. {Ort, BLand} {Vorwahl}

$$\rightarrow$$ 3. {PLZ} {BLand, Ort}

$$\rightarrow$$ 4. {Ort, BLand, Straße} {PLZ}

$$\rightarrow$$ 5. {BLand} {Landesregierung}

$$\rightarrow$$ 6. {Raum} {PersNr}

Hieraus können weitere Abhängigkeiten abgeleitet werden:

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

$$\rightarrow$$ 8. {PLZ} {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:

• Reflexivität: Aus $\beta$ $\subseteq$ $\alpha$ folgt: $\alpha$ $\rightarrow$ $\beta$
• Verstärkung: Aus $\alpha$ $\rightarrow$ $\beta$ folgt: $\alpha$$\gamma$ $\rightarrow$ $\beta$$\gamma$ für $\gamma$ $\subseteq$ U
• Transitivität: Aus $\alpha$ $\rightarrow$ $\beta$ und $\beta$ $\rightarrow$ $\gamma$ folgt: $\alpha$ $\rightarrow$ $\gamma$

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:

• Vereinigung: Aus $\alpha$ $\rightarrow$ $\beta$ und $\alpha$ $\rightarrow$ $\gamma$ folgt: $\alpha$ $\rightarrow$ $\beta$$\gamma$
• Dekomposition: Aus $\alpha$ $\rightarrow$ $\beta$$\gamma$ folgt: $\alpha$ $\rightarrow$ $\beta$ und $\alpha$ $\rightarrow$ $\gamma$
• Pseudotransitivität: Aus $\alpha$ $\rightarrow$ $\beta$ und $\gamma$$\beta$ $\rightarrow$ $\delta$ folgt $\alpha$$\gamma$ $\rightarrow$ $\delta$

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

• {PLZ} $\rightarrow$ {BLand} (Dekomposition von FD Nr.3)
• {BLand} $\rightarrow$ {Landesregierung} (FD Nr.6)
• {PLZ} $\rightarrow$ {Landesregierung} (Transitivität)

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

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

Es gilt der Satz:

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

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

X ⁰ : = $$\alpha$$

X ^{i + 1} : = X ⁱ $$\cup$$ $$\gamma$$  falls $$\beta$$ $$\rightarrow$$ $$\gamma$$ $$\in$$ F$$\land$$$$\beta$$ $$\subseteq$$ X ⁱ

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: X ^{i + 1} = X ⁱ.

Beispiel

:

Sei U = { A,B,C,D,E,G }

$$\rightarrow \rightarrow \rightarrow \rightarrow$$ Sei F =

$$\rightarrow \rightarrow \rightarrow \rightarrow$$

Sei X = { B,D }

X ⁰ = BD

X ¹ = BDEG

X ² = BCDEG

X ³ = ABCDEG = X ⁴, Abbruch.

Also: (BD)⁺ = ABCDEG

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

F $$\equiv$$ G $$\Leftrightarrow$$ F ⁺ = G ⁺

Zum Testen, ob F ⁺ = G ⁺, muß für jede Abhängigkeit $\alpha$ $\rightarrow$ $\beta$ $\in$ F überprüft werden, ob gilt: $\alpha$ $\rightarrow$ $\beta$ $\in$ G ⁺, d. h. $\beta$ $\subseteq$ $\alpha^{+}_{}$ . Analog muß für die Abhängigkeiten $\gamma$ $\rightarrow$ $\delta$ $\in$ 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 }

$$\rightarrow \rightarrow$$ Sei F = { AB C,

$$\rightarrow \rightarrow$$ C A,

$$\rightarrow \rightarrow$$ BC D,

$$\rightarrow \rightarrow$$ ACD B,

Aufspalten der rechten Seiten liefert

$$\rightarrow$$ AB C

$$\rightarrow$$ C A

$$\rightarrow$$ BC D

$$\rightarrow$$ ACD B

$$\rightarrow$$ D E

$$\rightarrow$$ D G

$$\rightarrow$$ BE C

$$\rightarrow$$ CG B

$$\rightarrow$$ CG D

$$\rightarrow$$ CE A

$$\rightarrow$$ CE G

$$\rightarrow \rightarrow$$ Regel ist redundant wegen C A

$$\rightarrow \rightarrow$$ ist redundant wegen CG D

$$\rightarrow$$ C A

$$\rightarrow$$ ACD B

$$\rightarrow \rightarrow \rightarrow$$ Regel kann gekürzt werden zu CD