Homework 7 (due 5/27)
CSC 355

We have talked about normalization, concentrating on BCNF i(Sections 3.3 and 3.4) and 3NF (Section 3.5). Section 3.4 also contains some general tools (such as the chase test). Next week (Wednesday, Monday is holiday) we'll talk about constraints and triggers (Chapter 7). Next topic after that will be views & indices (Chapter 8).
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.3, 3.4 and 3.5 of the textbook (Ullman, Widom, A First Course in Database Systems).

2. (Minimal Cover, 12pt) You are given a relation R(A,B,C,D,E,F) with functional dependencies F = {A→C, B→E, C→BF, DE→AB, E→DB, F→A}.

a) [8pt] Calculate a Minimal Cover for F.  Note: Do this one step at a time, and show the details.

b) [1pt] Calculate a Canonical Cover for F.

c) [3pt] Construct a 3NF decomposition of R with respect to F.

3. (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 decomposition). Use the algorithm we saw in class, and show each step clearly (what violation are you fixing in what relation, what is your decomposition after each step):

  1. R(A,B,C,D,E) with functional dependencies {A→BE, D→C, E→CD}.

  2. R(A,B,C,D,E) with functional dependencies {A→DE, B→CE, BA→CD}.

  3. R(A,B,C,D,E,F) with functional dependences {ABF→ D, AD→EF, AF→BC}.

4. (Lossless join chase test, 13pt) You have a relation R(A,B,C,D,E,F,G) with functional dependencies {A→G,B→A, BCE→ADF, D→EF, E→CD, G→BD}. A friend gave you the following decomposition: P(A,B,G), Q(B,C,D), S(D,E,F).

  1. [3pt] Is the decomposition in BCNF? (Argue your case.)

  2. [10pt] Use the chase test to determine whether the decomposition is a lossless join decomposition. Note: Apply one rule of the chase test in each step, and show the intermediate matrices.

5. (Extra Credit, 15pt) Implement an algorithm to calculate a BCNF decomposition of a given set of functional dependencies (input should be a string, e.g. BCNF('{A→BE, D→C, E→CD}') for problem 3a above). It is ok if the algorithm takes exponential time, but it needs to be correct (so it needs to resolve all BCNF violations, including hidden ones).

Marcus Schaefer
Last updated: May 22nd, 2014.