COS 597D, Fall 2013 - Assignment 5

Due 3:00pm,  Friday October 18, 2013
Note unusual date and time.   Submit by email or drop hard copy in bin outside Prof. LaPaugh's door.


Collaboration Policy

You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.

Late Penalties

10% of the earned score if submitted after 3:00pm  but by 11:59 pm Fri.
20% of the earned score if submitted by 11:59 pm on Mon. 10/21/13.
40% of the earned score if submitted after 11:59 pm on Fri. 10/21/13.


Problem 1:
Suppose that each functional dependency in a set Φ of functional dependencies on a relational scheme R satisfies the conditions for Third Normal Form (3NF).  Suppose we use Armstrong's transitivity rule to obtain X→Z  from X→Y and Y→ Z in Φ, where X, Y, and Z are sets of attributes of R.   Show that X→Z satisfies the conditions for 3NF in the case that neither X nor Y is a superkey.   Be precise.

Problem 2.
Consider a relational schema R with 5 attributes A, B, C, D, and E. Answer the following questions given the functional dependences

  1. A->ABCDE
  2. AB->D
  3. BCD->E
  4. E->B

Part a: For each of the 4 functional dependencies above, say whether the dependency satisfies the conditions of BCNF and of 3NF. If it does satisfy the conditions of a normal form, state precisely which condition for the normal form it satisfies (e.g. AB->B would be a "trivial" functional dependence satisfying both BCNF and 3NF).

Part b:  What is the lossless-join decomposition of R obtained by splitting out functional dependency BCD->E?   Is this decomposition dependency preserving? Is the resulting set of relational schemas in BCNF? in 3NF? Justify your answers by considering each functional dependency and showing that it does or does not satisfy the conditions of preserving dependency, of BCNF, and of 3NF.

Part c:  What is the lossless-join decomposition of R obtained by splitting out functional dependency E->B? Is this decomposition dependency preserving? Is the resulting set of relational schemas in BCNF? in 3NF? Justify your answers by considering each functional dependency and showing that it does or does not satisfy the conditions of preserving dependency, of BCNF, and of 3NF.