Funktionale Abhängigkeiten

Minimale Menge funktionaler Abhängigkeiten finden

• FDs (Functional Dependencies) rechte Seite aufteilen
  • A -> BC wird zu A -> B, A -> C
• Linksreduktion
  • Attribute auf der linken Seite, die von anderen Attributen auf der linken Seite abhängen werden entfernt
  • AB -> C, A -> B wird zu A -> C, A -> B
• Ableitbare FDs entfernen
  • Redundanz durch transitive Abhängigkeiten loswerden
  • A -> B, B -> C, A -> C wird zu A -> B, B -> C
• FDs rechte Seite zusammenführen
  • A -> B, A -> C wird zu A -> BC

Schlüsselmengen

• XL
  • alle Attribute, die auf keiner rechten Seite vorkommen
  • muss Teil jedes Schlüssels sein
• XR
  • alle Attribute, die auf keiner linken Seite vorkommen
  • ist nie Teil eines Schlüssels
• XB
  • alle Attribute, die auf beiden Seiten vorkommen
  • kann Teil eines Schlüssels sein
• Schlüsselkandidaten
  • Alle Vereinigungsmengen von XL und allen Teilmengen von XB
• Ist ein Schlüsselkandidat tatsächlich ein Schlüssel?
  • alle Attribute müssen teil der Attributhülle X* vom Schlüssel sein
    • Prüfen mit dem RAP-Algorithmus
      • Reflexivität
        • Initialisierung
        • alle Attribute des Schlüssels in X*
      • Akkumulation
        • Wähle eine FD, bei der alle Attribute der linken Seite bereits in X* sind
        • die Attribute der Rechten Seite sind von X* abhängig und somit jetzt auch in X*
        • wiederhole bis X* stabil
      • Projektion
        • Umfasst X* alle Attribute?
  • der Schlüssel muss minimal sein
    • deshalb mit den kleinsten Schlüsselkandidaten anfangen, die keine Teilmengen anderer noch nicht geprüfter Schlüsselkandidaten sind