Funktionale Abhängigkeit

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Funktionale Abhängigkeiten (Abk. FA, englisch functional dependency, FD) sind ein Konzept der relationalen Entwurfstheorie und bilden die Grundlage für die Normalisierung von Relationenschemata.

Eine Relation wird durch Attribute definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit. So könnte man sich etwa eine Kundendatenbank vorstellen, in der die Anschrift und die Telefonnummer eines Kunden eindeutig durch seinen Namen zusammen mit seinem Geburtsdatum bestimmt ist. Hier wären also Anschrift und Telefonnummer funktional abhängig von Name und Geburtsdatum.

Mit Hilfe funktionaler Abhängigkeiten lässt sich auch der Begriff Schlüssel definieren:

Bestimmen einige Attribute einer Relation eindeutig die Werte aller Attribute der Relation, so spricht man von einem Superschlüssel, das heißt, jedes Tupel dieser Relation ist eindeutig durch die Werte dieser Attribute bestimmt. Zum Beispiel könnte man eine Kundennummer einführen, die jeden Kunden identifiziert. Ein Schlüsselkandidat ist ein minimaler Superschlüssel, das heißt, keine echte Teilmenge der Attribute dieses Schlüssels bestimmt vollständig die Werte aller anderen Attribute der Relation. Unter allen Schlüsselkandidaten einer Relation wird ein so genannter Primärschlüssel ausgewählt.

Beispiel:

A	B	C
1	1	3
1	1	3
1	2	4

In diesem Beispiel ist C funktional abhängig von A, B, geschrieben also A, B → C. Der Pfeil kann somit gelesen werden als „bestimmt eindeutig“. Aber C ist nicht funktional abhängig von A allein. Es gelten auch die funktionalen Abhängigkeiten „A ist funktional abhängig von C“, „A ist funktional abhängig von B“ und „C ist funktional abhängig von B“.

Inhaltsverzeichnis

1 Formale Definition
2 Axiome von Armstrong
3 Normalisierung mit funktionalen Abhängigkeiten
4 Attributhülle
5 Abgeschlossene Hülle
6 Siehe auch

[Bearbeiten] Formale Definition

Sei r(R) eine Relation mit dem Relationenschema R und seien α und β Teilmengen von Attributen von R. Sei t ∈ R ein Tupel aus r. Dann ist t[α] die Einschränkung von t auf die Attribute aus α. Die funktionale Abhängigkeit α → β (β ist funktional abhängig von α) gilt auf R, wenn für jede zulässige Relation r(R) gilt:

$\forall t_1, t_2 \in r: t_1[\alpha]=t_2[\alpha] \implies t_1[\beta]=t_2[\beta]$

Das heißt, für alle Tupel t₁, t₂ ∈ r mit gleichen α-Attributen (t₁[α] = t₂[α]) gilt auch, dass ihre β-Attribute gleich sind (t₁[β] = t₂[β]). Die Werte der Attribute aus der Attributmenge α bestimmen also eindeutig die Werte der Attribute aus der Attributmenge β. Übrigens: Für Attributmengen schreibt man üblicherweise kurz αβ statt α⋃β.

β heißt voll funktional abhängig von α, wenn aus α kein Attribut entfernt werden kann, so dass die Bedingung immer noch gilt.

Im Beispiel oben spielt das Attribut 'A' für die Bestimmung von 'C' keine Rolle:

Aus der funktionalen Abhängigkeit AB → C lässt sich die volle funktionale Abhängigkeit B → C gewinnen.

[Bearbeiten] Axiome von Armstrong

Mit Hilfe der Axiome von Armstrong (auch Armstrong Axiome) lassen sich aus einer Menge von funktionalen Abhängigkeiten, die auf einer Relation gelten, weitere funktionale Abhängigkeiten ableiten. Die folgenden drei Regeln reichen aus, um alle funktionalen Abhängigkeiten herzuleiten:

1. Eine Menge von Attributen bestimmt eindeutig die Werte einer Teilmenge dieser Attribute (triviale Abhängigkeit), das heißt, $\beta\subseteq\alpha \Rightarrow \alpha \rightarrow \beta$ . (Reflexivität)

2. Gilt $\alpha \rightarrow \beta$ , so gilt auch $\alpha\gamma \rightarrow \beta\gamma$ für jede Menge von Attributen $γ$ der Relation. (Erweiterungsregel, Verstärkung)

3. Gilt $\alpha \rightarrow \beta$ und $\beta \rightarrow\gamma$ , so gilt auch $\alpha \rightarrow\gamma$ . (Transitivitätsregel)

Um Herleitungen einfacher zu gestalten, können zusätzlich die folgenden (abgeleiteten) Regeln verwendet werden:

4. Gelten $\alpha \rightarrow \beta$ und $\alpha \rightarrow \gamma$ , so gilt auch $\alpha \rightarrow \beta\gamma$ . (Vereinigungsregel)

5. Gilt $\alpha \rightarrow \beta\gamma$ , so gelten auch $\alpha \rightarrow \beta$ und $\alpha \rightarrow \gamma$ . (Dekompositions-/Zerlegungsregel)

6. Gilt $\alpha \rightarrow \beta$ und $\gamma \beta \rightarrow \delta$ , so gilt auch $\alpha \gamma \rightarrow \delta$ . (Pseudotransitivitätsregel)

[Bearbeiten] Normalisierung mit funktionalen Abhängigkeiten

Mit Hilfe von funktionalen Abhängigkeiten lassen sich Relationenschemata normalisieren. Ein Relationenschema R ist zum Beispiel in Boyce-Codd-Normalform, wenn für alle funktionalen Abhängigkeiten α → β, die auf R gelten, gilt: Die funktionale Abhängigkeit ist trivial oder α ist ein Superschlüssel für R. Die 3. Normalform ist etwas abgeschwächt. Für sie muss eine der oben angegebenen Bedingungen gelten oder dass alle Attribute aus β − α in einem Schlüsselkandidat (auch in verschiedenen) enthalten ist.

Es gibt Algorithmen, die ein Relationenschema auf der Grundlage funktionaler Abhängigkeiten in normalisierte Schemata zerlegen. Ziel einer solchen Zerlegung ist Verlustlosigkeit und Abhängigkeitsbewahrung der Zerlegung. Abhängigkeitsbewahrung bedeutet, dass alle funktionalen Abhängigkeiten die auf der ursprünglichen Relation gelten, auch auf der Zerlegung noch gelten. Ein solcher Algorithmus, der in die 3. Normalform transferiert ist der Synthesealgorithmus.

[Bearbeiten] Attributhülle

Die Attributehülle $α +$ eines bestimmten Attributs $α$ ist eine Liste aller Attribute, die von $α$ funktional abhängen. Im kleinsten Fall ist die Attributhülle nur das Attribut selbst, da keine anderen Attribute von ihm abhängen. Will man die Attributhülle eines Attributs bei einer gegebenen Anzahl funktionaler Abhängigkeiten F bestimmen, kann man einen einfachen Algorithmus anwenden:

1. Die Attributhülle $α +$ ist zunächst das Attribut selbst. Also $α + = α$

2. Für alle geltenden funktionalen Abhängigkeit $\beta \rightarrow \gamma$ wird ermittelt ob $β$ eine Teilmenge der Attributhülle $α +$ darstellt (die ja zunächst nur das Attribut $α$ selbst ist).

2.1 Wenn dies für eine funktionale Abhängigkeit zutrifft, dann füge die Attribute $γ$ zur Attributhülle hinzu.

2.2 Wenn nein, dann fahre mit der nächste funktionalen Abhängigkeit fort.

3. Wiederhole Schritt 2 solange, bis keine Attribute mehr zur Attributhülle hinzugefügt werden können.

Angewendet auf eine konkrete Menge an funktionalen Abhängigkeiten F:

F hat die Abhängigkeiten:
- $A,B \rightarrow C$
- $D \rightarrow E,F$
- $A \rightarrow G,H$
- $G \rightarrow B$
Wir wollen die Attributhülle für $A$ bestimmen.

1. $A + = A$

2. Durchlaufen der funktionalen Abhängigkeiten von oben nach unten:

- $A, B$ ist keine Teilmenge von $A$
- $D$ ist keine Teilmenge von $A$
- A ist Teilmenge von A
  - $A + = A + + G, H$
- G ist Teilmenge von A,G,H
  - $A + = A + + B$
- Neuer Durchlauf:
- A,B ist Teilmenge von A,G,H,B
  - $A + = A + + C$
- ...danach ändert sich nichts mehr an der Menge $A +$

[Bearbeiten] Abgeschlossene Hülle

Intuitiv gesprochen ist die abgeschlossene Hülle einer Menge von funktionalen Abhängigkeiten die Menge der Attribute, die durch die „linken Seiten“ der Abhängigkeiten bestimmt ist.

Ist F ={α₁ → β₁,...,α_n → β_n} eine Menge von funktionalen Abhängigkeiten, so ist die abgeschlossene Hülle oder Attributhülle die Menge

$\bigcup_{\alpha_1...\alpha_n \to \gamma} \gamma$