CHAPTER 7

7.1 See the body of the chapter.

7.2 The closure F+ of a set F of FDs is the set of all FDs implied by those in F. The closure of the set of FDs that hold in the shipments relvar SP is given in the answer to Exercise 4.1.

7.3 The FD X → Y is satisfied if and only if whenever two tuples agree on X, they also agree on Y (I’m deliberately giving this definition in a pretty loose form). So:

  • If two tuples agree on X, they certainly agree on every subset Y of X, so the reflexivity rule is reasonable.

  • If two tuples agree on XZ, they certainly agree on Z. They also certainly agree on X and hence, if X → Y is satisfied, on Y as well; hence they agree on YZ, and so the augmentation rule is reasonable.

  • If two tuples agree on X and X → Y is satisfied, they agree on Y. If they agree on Y and Y → Z is satisfied, they agree on Z. So the transitivity rule is reasonable.

7.4 See the body of the chapter.

7.5 Let U denote the intersection of Z and Y and let V denote the difference Z – Y between Z and Y (in that order). Then:

  1. X → Y (given)

  2. Z → W (given)

  3. X → U (1, decomposition)

  4. XV → UV (3, augmentation)

  5. XV → Z (simplifying 4)

  6. XV → W (5, 2, transitivity)

  7. XV → YW (1, 6, composition; this completes the proof)

The rules used in this proof are indicated in the comments. The following rules are all special cases of Darwen’s theorem: the union, transitivity, and augmentation rules. So too is the following useful rule:

  • If X → Y and XY → Z, then X → Z.

Note: This latter is a special case of what’s sometimes called the pseudotransitivity rule, which in its general form looks like this:

  • If X → Y and YW → Z, then XW → Z.

7.6 The first step is to rewrite the given set of FDs such that every FD has a singleton right side:

  1. AB → C

  2. C → A

  3. BC → D

  4. ACD → B

  5. BE → C

  6. CE → A

  7. CE → F

  8. CF → B

  9. CF → D

  10. D → E

  11. D → F

Now:

  • 2 implies 6, so we can drop 6.

  • 8 implies CF → BC by augmentation, which with 3 implies CF → D by transitivity, so we can drop 9.

  • 8 implies ACF → AB by augmentation, and 11 implies ACD → ACF by augmentation, and so ACD → AB by transitivity, and so ACD → B by decomposition, so we can drop 4.

No further reductions are possible, and so we’re left with the following irreducible cover:

     AB  → C
     C   → A
     BC  → D
     BE  → C
     CE  → F
     CF  → B
     D   → E
     D   → F

Alternatively:

  • 2 implies 6, so we can drop 6 (as before).

  • 2 implies CD → AD by augmentation, which implies CD → ACD by augmentation again, which with 4 implies CD → B by transitivity, so we can replace 4 by CD → B.

  • 2 and 9 imply CF → AD by composition, which implies CF → ADC by augmentation, which with (the original) 4 implies CF → B by transitivity, so we can drop 8.

No further reductions are possible, and so we’re left with the following irreducible cover:

     AB  → C
     C   → A
     BC  → D
     CD  → B
     BE  → C
     CE  → F
     CF  → D
     D   → E
     D   → F

Observe, therefore, that there are (at least) two distinct irreducible covers for the original set of FDs. Note too that those two covers have different cardinalities.

7.7 Yes, it is. The easiest way to prove this result is to compute the closure ACF+ of the set ACF, which turns out to be the entire set ABCDEFG. Alternatively, we can apply Armstrong’s axioms and the other rules discussed in the body of the chapter, as follows:

  1. A → B (given)

  2. ACF → BCF (1, augmentation)

  3. BC → E (given)

  4. BCF → EF (3, augmentation)

  5. ACF → EF (2, 4, transitivity)

  6. ACF → AEF (5, augmentation)

  7. AEF → G (given)

  8. ACF → G (6, 7, transitivity)

  9. BC → DE (given)

  10. BC → D (9, decomposition)

  11. BCF → DF (10, augmentation)

  12. BCF → D (11, decomposition)

  13. ACF → D (2, 12, transitivity)

  14. ACF → DG (7, 13, composition)

7.8 Let’s number the FDs of the first set as follows:

  1. A → B

  2. AB → C

  3. D → AC

  4. D → E

Now, 3 can be replaced by:

3. D → A and D → C

Next, 1 and 2 together imply (see the “useful rule” mentioned near the end of the answer to Exercise 7.5) that 2 can be replaced by:

2. A → C

But now we have D → A and A → C, so D → C is implied by transitivity and can be dropped, leaving:

3. D → A

The first set of FDs is thus equivalent to the following irreducible cover:

     A → B
     A → C
     D → A
     D → E

The second given set of FDs

     A → BC
     D → AE

is clearly also equivalent to this same irreducible cover. The two given sets are thus equivalent.

7.9 The set is clearly reducible, since C → J and CJ → I together imply C → I. As for keys: An obvious superkey is ABCDGJ (the combination of all attributes mentioned on the left sides of the given FDs). We can drop J from this set because C → J, and we can drop G because AB → G. Since none of A, B, C, D appears on the right side of any of the given FDs, it follows that ABCD is a key.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset