Homework 5 (due 2/25)
CSC 355


We talked about transactions (Section 6.6) and then went back to relational design (Chapter 3), beginning with functional dependencies, closure and equivalence (3.1, 3.2). Next week, we will talk about minimal covers and canonical covers (3.2) and normal forms:BCNF (3.3) and 3NF (3.5) and tools for evaluating decompositions (3.4).



Handing it in: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns.

1. (Reading Assignment) Read Sections 3.1 and 3.2 (o the end of 3.2.6) of the textbook (Ullman, Widom, A First Course in Database Systems).

2. (Closures, 7pt) You have a relation R(A,B,C,D,E,F) and a set of functional dependencies F = {AB CE, B C, C AD, BDE F}.

3. (Inference, 6pt) You have a relation R(A,B,C,D,E,F) and a set of functional dependencies F = {ACD→B, BC→AED, C→D, DE→AC}.

  • [3pt] Can we infer CE → AB from F ?

  • [3pt] Can we infer CF → AD from F ?

4. (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.

5. (Keys, 12pt) You have a relationship R(A,B,C,D,E,F) with functional dependencies {BC→A, BD→F, CE→B, DF→E, F→D}. Determine all keys (minimal superkeys) of R. Be sure to explain why each key you identified is a key, and why there are no other keys than the ones you found. Hint: there are three keys.

6. (Extra Credit, 10pt) Implement a program that takes as input a relation R and a set of functional dependencies over R and prints out all keys (not superkeys) of R. (You can use this program to solve 4.)

7. (Extra Credit, requires some combinatorics, 8pt) Show that a relation R on n attributes may have as many as n! / ((n/2)! * (n/2)!), that is n choose n/2, many keys. You need to argue that all the keys are actually keys, not just superkeys.


Marcus Schaefer
Last updated: February 18th, 2014.