FDs Consider relation RABCDE with functional dependencies AB

(FD’s) Consider relation R(A,B,C,D,E) with functional dependencies AB->C, BC->D, CD->E, DE->A, and AE->B. Which FD’s hold on the projected relation S(A,B,C,D)?

Solution

\"Project these FD\'s onto the relation S(A,B,C,D)\" is sloppy writing. (Although you comment that you are quoting your assignment.) Presumably this is trying to say, if these FDs hold in R(ABCDE) then which of the following FDs holds in its projection on ABCD.

When some FDs hold, other ones must also hold because those ones do. Thus many more FDs hold in R than the ones you were given. Moreover some of the FDs that hold but aren\'t given hold because some of the FDs using E hold--even though they themselves do not contain E. So first you need to find more of the FDs in R, until you find one that will be kept after projecting since they don\'t involve E.

One way is to find F+ (the closure of the set of FDs). But it can be very large. What we can do instead is use the notion of a closure of an attribute set. That is the set of all attributes determined by an attribute set. (From the determined attributes we know all the FDs that hold with that determinant.) There is an algorithm for finding it. If an answer FD determinant is a determinant in F then we can calculate its closure in R to see if its answer FD also holds in R.

If none of the determinants of the FDs appeared as determinants in F then we would have to start generating FDs in F+ until we got one with a determinant that was also a determinant among the answers. Then we could apply the previous step.