We have started talking about normalization, and BCNF in particular, see Sections 3.3 and 3.4. We will continue with 3NF (3.6), and then go on to talk about constraints and triggers (Chapter 7). Next topic after that will be views & indices (Chapter 8).
1. (Reading Assignment) Read Sections 3.3 and 3.4 of the textbook (Ullman, Widom, A First Course in Database Systems).
2. (Minimal Cover, 10pt) You are given a relation R(A,B,C,D,E,F) with functional dependencies F = {A→C, B→GE, C→BF, DEF→ABG, E→DB, F→A}.
a) [9pt] 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.
3. (BCNF, 20pt) Decompose the following relations into BCNF and for each decomposition determine whether it is dependency-preserving. Use the algorithm we saw in class:
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, B→CE, BA→CD}.
R(A,B,C,D,E,F) with functional dependences {ABF→ D, AD→EF, AF→BC}.
R(A,B,C,D,E,F) with functional dependencies {A→BC, BD→AE, DF→ACE}.
4. (Lossless join chase test, 10pt) 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).
Is the decomposition in BCNF? (Argue your case.)
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).