EXERCISES

7.1 What does it mean to say that Armstrong’s rules are sound? Complete?

7.2 What’s the closure of a set of FDs? Show the closure of the set of FDs that hold in the shipments relvar SP.

7.3 Given the definition of what it means for an FD to be satisfied, show that the reflexivity, augmentation, and transitivity rules are reasonable.

7.4 (Try this exercise without referring back to the body of the chapter.) Prove that the three rules of the previous exercise imply the self determination, union, composition, and decomposition rules.

7.5 The following theorem is due to Hugh Darwen:^[70]

• If X → Y and Z → W, then XV → YW, where V = Z − Y.

Prove this theorem. Which rules from the previous two exercises did you use? Which rules from those exercises can be derived as special cases of the theorem?

7.6 Find an irreducible cover for the following set of FDs:

     AB  → C      BE → C
     C   → A      CE → FA
     BC  → D      CF → BD
     ACD → B      D  → EF

7.7 Consider the following FDs:

     A   → B
     BC  → DE
     AEF → G

Is the FD ACF → DG implied by this set?

7.8 Two sets of FDs are equivalent if and only if each is a cover for the other. Are the following sets equivalent?

     { A → B , AB → C , D → AC , D → E }
     { A → BC , D → AE }

Note that any given set F of FDs is certainly equivalent to a set C if C is an irreducible cover for F, and further that two sets are equivalent if and only if they have the same irreducible cover.

7.9 Relvar R has attributes A, B, C, D, E, F, G, H, I, and J, and is subject to the following FDs:

     ABD → E        C  → J
     AB  → G        CJ → I
     B   → F        G  → H

Is this set reducible? What keys does R have?

---

^[70] Hugh Darwen: “The Role of Functional Dependence in Query Decomposition,” in C. J. Date and Hugh Darwen, Relational Database Writings 1989-1991 (Addison-Wesley, 1992).