We talked about relational design (Chapter 3), beginning with functional dependencies, closure and equivalence (3.1, 3.2)., followed by minimal covers and canonical covers (3.2), and normal forms, BCNF (3.3) in particular. Next week, we will talk about the chase test for checking the loss-less join property (3.4) and 3NF (3.5), for which we'll use the minimal cover, and then move on to Constraints and Triggers (Chapter 7).
1. (Reading Assignment) Read Sections 3.2.1-3.2.6, and 3.3 of the textbook (Ullman, Widom, A First Course in Database Systems).
2. (Functional Dependencies, 15pt) You have a relation R(A,B,C,D, E) and a set of functional dependencies F = {A→C, B→E, BD→C, CD→BE, DE→A}.
[5pt] You show this to your friend Alice, who claims that you can simplify your set of dependencies to G = {A→C, B→E, BD→C, CD→B, DE→A}. Is she right, i.e., are the two sets of functional dependencies equivalent?
[5pt] You also show your FDs to your friend Bob, who comes up with a different modification: G = {A→C, B→E, D→C, CD→BE, DE→A}. Is his version equivalent to your original set?
[5pt] You finally share your FDs with your friend Carol, who suggests: G = {A→C, B→E, CD→B, DE→A}. Is Carol right, i.e. is his set of functional dependencies equivalent to your original set?
Hint: For each of these problems you have to determine whether two sets of functional dependencies F and G are equivalent. To argue that they are, you need to argue that each FD in G can be inferred from F, and each FD in F can be inferred from G (for many of the FDs that is the case because they occur in both sets, so no elaborate argument is needed). To argue that they are not you need to find and exhibit an FD in F that doesn't follow from G or vice versa.
3. (Minimal Cover, 10pt) You are given a relation R(A,B,C,D,E,F) with functional dependencies F = {A→BC, ABE→D, AE→B, EF→AC}.
a) [8pt] Calculate a Minimal Cover for F. Note: Do this one step at a time, and show the details.
b) [2pt] Calculate a Canonical Cover for F.
4. (BCNF, 15pt) Decompose the following relations into BCNF and for each decomposition determine whether it is dependency-preserving (that is, do all dependencies survive in the decomposed tables). Use the algorithm we saw in class, and show each step clearly (which FDs are violations, which violation are you fixing in what relation, what is your decomposition after each step):
R(A,B,C,D,E) with functional dependencies {A→BE, D→C, E→CD}.
R(A,B,C,D,E) with functional dependencies {A→DE, AB→CD, B→CE}.
R(A,B,C,D,E,F) with functional dependences {ABF→ D, AD→EF, AF→BC}.
5. (Extra Credit, 15pt) Implement a program that takes as input a relation R and computes a Canonical Cover of R. You can use this program to solve problem 3.