Prove that all rules for inferring FDs and MVDs are sound. In other words, for every relation, r, which satis?es the dependencies in the premise of any rule, R, the conclusion of R is also satis?ed by r (e.g., for the augmentation rule, prove that if X ?? Y holds in r then X Z ?? Y also holds in r).

Question

What will be an ideal response?

Answer 1

The proof uses a technique, which we used for proving the soundness of Armstrong’s axioms. However, the reasoning is much more involved. To illustrate, we prove the soundness of the transitivity axiom

X ?? Y and Y ?? Z entail X ?? Z ? Y .

Most of the other proofs are every bit as tedious.
Let R be the set of all attributes in the schema. Then we have the following binary join dependencies:

JD1: R = XY  X (R ? Y )
JD2: R = YZ  Y (R ? Z )

We need to showthat every relation, r, that satis?es these two JDs also satis?es the following JD:

X (Z ? Y )  X (R ? (Z ? Y ))

To see this, let t be a tuple over R such that ?X(Z ?Y )(t ) ?X (Z ?Y )(r) and ?X (R?(Z ?Y ))(t ) ? ?X(R?(Z ?Y ))(r). To prove the soundness of the inference rule we need to show that t ? r.
The proof relies on the result of exercise 6.31(a). According to this result, the projection of JD1 on XYZ holds in ?XYZ(r).
Now notice that the intersection of X(Z ? Y ) and XYZ is X (Z ? Y ) and the intersection of X (R ? (Z ? Y )) with XYZ is XY . Also notice that X (Z ? Y ) is the intersection of XYZ with X(R ? Y ).
This means that ?X(Z ?Y )(t ) ? ?X(Z ?Y )(r) (as we saw earlier) and ?XY(t ) ??XY(r). Since the projection of JD1 on XYZ holds in ?XYZ(r), it means that ?XYZ(t ) ? ?XYZ(r). In particular, ?YZ(t ) ? ?YZ(r).
Since ?X(R?(Z ?Y ))(t ) ? ?X(R?(Z ?Y ))(r) (by assumption) and R ? (Z ? Y )=Y (R ? Z ), it follows that both ?YZ(t ) ? ?YZ(r) and ?Y (R?Z)(t ) ? ?Y(R-Z)(r). Because JD2 holds in r, it follows that t ? r, which completes the proof.
The above proof (and the proofs for other rules) can be simpli?ed somewhat by making the left and right hand sides of the MVDs disjoint. This is possible because it is easy to show(directly from the de?nitions) that the MVD X ?? Y is equivalent to
X ?? (Y ? X ).
XY