relationale Algebra; Umformungen

Question

Aufgabe:

Beweisen Sie mittels der drei Armstring-Axiome, Transitivitätsregel, Erweiterungsregel und Reflexivitätsregel, dass die Vereinigungsregel und die Pseudotransitivitätsregel gelten. Geben Sie für jeden Beweisschritt die jeweils verwendete Regel an.

Beweisen Sie folgende Aussage: Seien \( A \rightarrow B, A \rightarrow C, C B \rightarrow D \) bekannte funktionale Abhängigkeiten, dann gilt auch die funktionale Abhängigkeit \( A \rightarrow D \). Geben Sie für jeden Beweisschritt die jeweils verwendete Regel an.

Problem/Ansatz:

trans.: \( X \rightarrow Y \wedge Y \rightarrow Z \Rightarrow X \rightarrow Z \)

erw.: \( X \rightarrow Y \Rightarrow X \cup Z \rightarrow Y \cup Z \)

refl.: \( X \supseteq Y \Rightarrow X \rightarrow Y \)

vereinigung:$$  X \rightarrow Y \wedge X \rightarrow Z \Rightarrow X \rightarrow Y \cup Z $$

zerlegung: $$  X \rightarrow Y \cup Z \Rightarrow X \rightarrow Y \wedge X \rightarrow Z $$

pseudotransitivität: $$  X \rightarrow Y \wedge W \cup Y \rightarrow Z \Rightarrow W \cup X \rightarrow Z $$

ich hab leider keine Ahnung wie ich hier vorgehen kann. Kann mir vielleicht einer einen kleinen Denkanstoß bzw. Ansatz geben damit ich weiß wie ich anfangen kann?

Answer 1

Hallo,

vielleicht ist ein Beispiel gut, um die anderen anzugehen.

Die Vereinigungsregel sagt: Aus \(X \to Y\) und \(X\to Z\) folgt, dass \(X\to Y\cup Z\).

Aus \(X\to Y\) kann man mit der Erweiterungsregel auf eine beliebige Attributmenge \(Z\) schließen: $$X\cup Z \to Y\cup Z$$ Analog kann man aus \(X\to Z\) durch Erweiterung mit \(Y\) auch folgendes erhalten:$$X\cup Y\to Z\cup Y$$ Also insbesondere$$X\to Y \land \, X\to Z \implies X\to Y\cup Z$$ Bei der Pseudotransitivitätsregel musst du die Erweiterungsregel anwenden und die Transitivität auf den dann erweiterten Ausdruck.