# 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
      - **R**eflexivität
        - Initialisierung
        - alle Attribute des Schlüssels in `X*`
      - **A**kkumulation
        - 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
      - **P**rojektion
        - 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