Aufgabe 9.5 (20 Punkte)

Beweisen Sie die Korrektheit der drei zusätzlich zu den Armstrong-Axiomen eingeführten Axiome (Vereinigung, Dekomposition und Pseudotransitivität) für funktionale Abhängigkeiten, indem Sie sie aus den Armstrong-Axiomen herleiten.

Musterlösung vom 29.06.2009:

Die Armstrong-Axiome sind wie folgt definiert, wobei $\alpha$, $\beta$, $\gamma$ und $\delta$ Teilmengen der Attribute aus dem Relationenschema $R$ bezeichnen.

• Reflexivität: $\beta \subseteq \alpha \Rightarrow \alpha \rightarrow \beta$

• Verstärkung: $\alpha \rightarrow \beta \Rightarrow \alpha\gamma \rightarrow \beta\gamma$

• Transitivität: $\alpha \rightarrow \beta \wedge \beta \rightarrow \gamma \Rightarrow \alpha \rightarrow \gamma$

Beweis der drei zusätzlich hergeleiteten Axoime:

• Vereinigung: $\alpha \rightarrow \beta \wedge \alpha \rightarrow \gamma \Rightarrow \alpha \rightarrow \beta\gamma$

  Beweis: Verstärkung von $\alpha \rightarrow \beta$ mit $\alpha$:

  
  

  $$\alpha\alpha \rightarrow \alpha\beta \Leftrightarrow \alpha \rightarrow \alpha\beta$$
  
  

  Verstärkung von $\alpha \rightarrow \gamma$ mit $\beta$:

  
  

  $$\alpha\beta \rightarrow \gamma\beta \Leftrightarrow \alpha\beta \rightarrow \beta\gamma$$
  
  

  Wegen der Transitivität folgt:

  
  

  $$\alpha \rightarrow \alpha\beta \wedge \alpha\beta \rightarrow \beta\gamma \Rightarrow \alpha \rightarrow \beta\gamma$$
  
  

• Dekomposition: $\alpha \rightarrow \beta\gamma \Rightarrow \alpha \rightarrow \beta \wedge \alpha \rightarrow \gamma$

  Beweis: Wegen der Reflexivität gilt aufgrund von $\beta \subseteq \beta\gamma$:

  
  

  $$\beta\gamma \rightarrow \beta$$
  
  

  Wegen der Reflexivität gilt aufgrund von $\gamma \subseteq \beta\gamma$:

  
  

  $$\beta\gamma \rightarrow \gamma$$
  
  

  Wegen der Transitivität folgt dann:

  
  

  $$\alpha \rightarrow \beta\gamma \wedge \beta\gamma \rightarrow \beta \Rightarrow \alpha \rightarrow \beta$$
  
  

  und:

  
  

  $$\alpha \rightarrow \beta\gamma \wedge \beta\gamma \rightarrow \gamma \Rightarrow \alpha \rightarrow \gamma$$
  
  

• Pseudotransitivität: $\alpha \rightarrow \beta \wedge \gamma\beta \rightarrow \delta \Rightarrow \alpha\gamma \rightarrow \delta$

  Beweis: Verstärkung von $\alpha \rightarrow \beta$ mit $\gamma$:

  
  

  $$\alpha\gamma \rightarrow \beta\gamma \Leftrightarrow \alpha\gamma \rightarrow \gamma\beta$$
  
  

  Wegen der Transitivität folgt:

  
  

  $$\alpha\gamma \rightarrow \gamma\beta \wedge \gamma\beta \rightarrow \delta \Rightarrow \alpha\gamma \rightarrow \delta$$