We have shown the soundness of the algorithm in Figure 6.3—that if A ? closure then A ? X + F .Prove the completeness of this algorithm; that is, if A ? X + F ,then A ? closure at the end of the computation.

Question

Use induction on the length of derivation of X ? A by Armstrong’s axioms.

Answer 1

Since A ? XF and because of the completeness of the Armstrong’s axioms, there must be a derivation of X ? A. We prove that A ? closure by induction on the length, n, of this derivation. More speci?cally, the induction will show a more general claim: if W ? V , where W ? closure, can be derived by Armstrong’s axioms, then V ? closure. Since X ? closure, the above would imply that if X ? A ? F+ then A ? closure.
Case n = 1: This is only possible if the rule used in such a 1-step derivation is the Re?exivity axiom or is an FD from F. In case of the Re?exivity axiom, we must already have V ? W ,for some W ? closure, and so we conclude that V ? closure. In case W ? V ? F, where W ? closure, V must be a subset of closure by construction: during the iteration when W was determined to be in closure, the right-hand side of the FD (i.e., V ) will be added.
Inductive step: Assume that, for any set V ,if W ? V (where W ? closure) can be derived via n steps, then V ? closure.
Suppose W ? V ,whereW ? closure, was derived using n +1 derivation steps (and no less). If the last rule in the derivation was Re?exivity, then V ? W and, since W ? closure, it follows that V ? closure.
If the last step was Augmentation, then W ? U (U = ?) was derived at step n or earlier, and then augmented with a nonempty set of attributes Z , such that W 'Z = W and UZ = V .Since W ? W ? closure, it follows by the inductive assumption that U ? closure. Since Z ? W ? closure, it follows that V ? closure.
If the last step in the derivation was transitivity, it means that the following two FDs were derived earlier: W ? U and U ? V . By the inductive assumption, U ? closure and, hence, V ? closure.