CHAPTER 11

11.1 Which JDs are trivial? None. Which ones involve irrelevant components? i., k., and l. Which imply others? a. implies b.; d. implies g. and h.; e. implies g.; f. implies h. and i.; j. implies k. Which pairs are equivalent? None. Which are satisfied by the sample value in Figure 1-1? a., b., c., d., e., g., and l. Which hold in relvar P? a., b., c., e., and l. Which are irreducible? a., b., c., and e.

11.2

  1. By Heath’s Theorem, the answer is obviously yes (take X as A, Y as BC, and Z as D). But let’s see if we can prove this result using the chase. Premise tuples:

          x1  y12  y13   x4
      x1   x2   x3  y24

    From the FD A → B, we have y12 = x2; from the FD A → C, we have y13 = x3. Make the replacements:

          x1   x2   x3   x4
      x1   x2   x3  y24

    Now we have a tuple of all x’s, and the desired result follows. The given JD does follow from the given JDs.

  2. Premise tuples:

          x1   x2  y13  y14
     y21   x2   x3  y24
     y31  y32   x3   x4

    The FDs imply y24 = x4 and y13 = x3. Make the replacements:

          x1   x2   x3  y14
     y21   x2   x3   x4
     y31  y32   x3   x4

    The FD C → D now implies y14 = x4; making the replacement gives us a tuple of all x’s, and so the result follows: The given JD does follow from the given FDs. Note that we had to use one of the FDs twice in the chase in this example. Note too that we could have obtained the same result by applying Heath’s Theorem twice: The FD C → D implies the JD {CD,CAB}, which in turn implies the JD {CD,BC,BA}, thanks to the FD B → C.

  3. I leave it to you to show the answer here is no.

  4. Premise tuples:

          x1   x2  y13  y14
     y21   x2   x3  y24
     y31  y32   x3   x4

    Applying the JD {BC,ABD} to the tuples with a common B value (viz., x2) generates the following tuples:

          x1   x2   x3  y24
     y21   x2  y13  y14

    We don’t obtain a tuple of all x’s, and so the “target” JD doesn’t follow from the given one; in fact, we now have a sample relation (of five tuples) that satisfies the latter and not the former.

11.3 Here first is a proof of part (b) of the extended theorem:

  1. X → Y (given)

  2. XZ → YZ (augmentation)

  3. XZ → XZ (self determination)

  4. XZ → XYZ (2 and 3, union)

Hence XZ is a superkey for R.

As for the converse, suppose relvar R contains the following tuples:

     x  y1  z1
     x  y2  z2

Thanks to the JD {XY,XZ}, the following tuples must then also appear:

     x  y1  z2
     x  y2  z1

But XZ is a superkey and so XZ → Y holds, so y1 = y2; hence X → Y holds.

11.4 This exercise is discussed further in Chapter 14, but I give a preliminary discussion here. First of all, suppose such a decomposition (i.e., on the basis of the second JD) were done. Let the projections so obtained be labeled SNC and CTN in the obvious way. Then the projections of SNC and CTN on {SNAME,CITY} are clearly equal; that is, the following equality dependency holds (see Chapter 13)—

     CONSTRAINT ... SNC { SNAME , CITY } = CTN { SNAME , CITY } ;

—and relvars SNC and CTN thus suffer from redundancy.

Observe further that the FD {CITY} → {STATUS} holds in CTN. By Heath’s Theorem, therefore, we can decompose CTN into its projections CT and CN on {CITY,STATUS} and {CITY,SNAME}, respectively. It follows that the JD

      { { SNO , SNAME , CITY } , { CITY , STATUS , SNAME } }

implies the JD

      { { SNO , SNAME , CITY } , { CITY , STATUS } , { CITY , SNAME } }

In this latter JD, however, the {CITY,SNAME} component is clearly irrelevant, since it’s a proper subset of the {SNO,SNAME,CITY} component; it can therefore be dropped without significant loss. (In fact, of course, this latter JD is identical to the first of the two JDs as given in the original exercise.)

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

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