We talked functional dependencies, closure and equivalence (3.1, 3.2), minimal covers and canonical covers (3.2) and normal forms:BCNF (3.3) and 3NF (3.5) and tools for evaluating decompositions, including the chase test (3.4).
1. (Reading Assignment) Read Sections 3.1-3.5 of the textbook.
2. (Minimal and Canonical Cover, 10pt) You are given a relation R(A,B,C,D,E,F,G) with functional dependencies F = {A→C, B→GE, C→BF, DEF→ABG, E→DB, F→A}.
a) [8pt] Calculate a Minimal Cover for F. Note: Do this one step at a time, and show the details. Keep the three phases separate.
b) [2pt] Calculate a Canonical Cover for F.
3. (3NF, 5pt) You are given a relation R(A,B,C,D,E,F) with canonical cover F = {A→E, B→DE, E→A, F→AC}.
a) [1pt] Find the (unique) key of R.
b) [4pt] Find a 3NF decomposition of R based on the canonical cover and your answer in a).
4. (BCNF, 15pt) 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 dependencies {A→BC, BD→AE, DF→ACE}.
5. (Lossless join chase test, 10pt) You have a relation R(A,B,C,D,E,F) with functional dependencies {AC→B, B→DE, C→F, D→EF, DF→A}. A friend gave you the following decomposition of R into three tables: P(A,B,C), Q(C,D,E), S(A,D,F).
[2pt] Is this decomposition in BCNF? (Explain why or why not.)
[8pt] Use the chase test to determine whether the decomposition your friend gave you is a lossless join decomposition. Note: Apply one rule of the chase test in each step, and show the intermediate tables (or, as they are sometimes called, tableaus) you get.
6. (Extra Credit, 10pt) Implement a program that given a set of FDs for a relation R, and a specific attribute of R, determines whether that attribute is prime or not.