Homework 5 (due 5/9)
CSC 453

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

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-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:

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

  1. [2pt] Is this decomposition in BCNF? (Explain why or why not.)

  2. [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.

Marcus Schaefer
Last updated: May 4th, 2018.