Search code examples
functional-dependencies

projecting functional dependencies onto another relation

consider the relation R(ABCDE) with the following FD's:

  • AB -> C
  • BC -> D
  • CD -> E
  • DE -> A
  • AE -> B

Project these FD's onto the relation of S(ABCD). Which of the following FD's hold in the projected relation?

  1. A -> B
  2. A -> D
  3. BC -> A
  4. AC -> B

the wording in the above question is directly copied from an assignment

The correct answer is given to be 3.

since the last 3 FD's contain E they do not hold in the projection onto R(ABCD) I believe. So that leaves me with AB -> C and BC -> D I can not figure out how to determine the correct answer from my current though process.

Solution

  • Your question is not clear. I am assuming that you are asking which of the last four dependencies hold in the relation R(ABCD): the answer is the third. This can be simply proved by computing the closure of BC in the original set of dependencies:

    BC+ = BC
BC+ = BCD    (using BC → D)
BC+ = BCDE   (using CD → E)
BC+ = BCDEA  (using DE → A)

    so, BC is a candidate key and determines A, so that BC → Aholds also in R(ABCD). If you try to compute the closure for all the other left hand sides of the four dependencies, you will never find the right side, so they do not hold in R(ABCD).

    Why the answer can be obtained by computing the closure of the determinant?

    Let's call FS the projection of the original set of dependencies F over the relation S(ABCD). So, for the definition of the projection of a set of dependencies, we have that:

    FS = { X → Y ∈ F+ | X,Y ⊆ ABCD }

    and the question asks if certain dependencies belong to FS. But since the computation of FS requires the computation of F+, which is an exponential task, instead of calculating it, we check, for each of the four dependencies X → Y, if it belongs to F+. This is equivalent to the polynomial task of calculating the closure of X and finding if Y belong to it or not (we already know that the dependencies have all the attributes in the set ABCD).

    So the answer is to calculate the closure of all the left hand parts of the dependencies and see if the right part is contained in it or not. And this is true only for the third dependency.