﻿

## Homework 6 (due 5/20) 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)., followed by minimal covers and canonical covers (3.2). Next week, we'll see two normal forms in detail: BCNF (3.3) and 3NF (3.5), for which we'll use the minimal cover, 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 = {A F, AB EF, ACE→ D, F BC}.

• [2pt] Determine F+. Does F determine D?

• [2pt] Determine EF+. Does EF determine D?

• [3pt] Find a key of R. Is it unique (that is, is it the only key)? (If it's not unique, find another key, if it is unique, justify why.).

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

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

• [3pt] Can we infer CE → 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 {AD→F, AF→B, C→E, EC→D, EF→C}. Determine all keys (minimal superkeys) of R. Be sure to explain why

1. [9pt] each key you identified is a key, and

2. [3pt] why there are no other keys than the ones you found.

Hint: there are three keys. You cannot use this fact in your argument for b, it's just supposed to help you with a).

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 problem 5.)

Marcus Schaefer
Last updated: May 14h, 2014.