Attributhülle und Membership-Problem

Die Hülle einer Attributmenge $X$ unter einer Menge von FDs $S$ (notiert als $X^{+}$) ist die Menge aller Attribute, die sich funktional aus $X$ ableiten lassen.

Das Membership-Problem klärt die Frage: "Gilt eine bestimmte FD $X\to Y$ unter den gegebenen Regeln?". Dies wird bejaht, wenn $Y\subseteq X^{+}$.

Lösungsschema: Berechnung der Hülle ($X^{+}$)

1. Initialisierung: Setze die Ergebnismenge gleich der Startmenge der Attribute (die linke Seite der zu prüfenden FD).
2. Suchen: Suche wiederholt in der Liste der FDs nach Regeln der Form $B_1,\dots ,B_m\to C$, bei denen die linke Seite bereits vollständig in der Ergebnismenge enthalten ist, aber $C$ noch nicht.
3. Erweitern: Füge $C$ zur Ergebnismenge hinzu.
4. Terminierung: Wiederhole Schritt 2 und 3, bis in einem kompletten Durchlauf keine neuen Attribute mehr hinzugefügt werden können.

Links

• Funktionale Abhängigkeit (FD)
• ISDA 04 Relationale Entwurfstheorie.pdf