The Databases Course

Exercise No. 6

Design Theory

Due on January 1st (1998!) by midnight

 

  1. Armstrong's axioms for inferring functional dependencies are just one example of an axiom system. Consider the following axiom system:

    Reflexivity: X ® X
    Accumulation: X ® YZ, Z ® CW ¦ X ® YZC
    Projectivity: X ® YZ ¦ X ® Y

    Prove that these axioms are sound, and that Armstrong's axioms can be derived from them.

  2. Let R be a relation with S = { A, B, C, D, E, F } and F = { A ® BC , BD ® E , B ® C , ACF ® E , BC ® F , AD ® C }.
  1. Find a non-redundant (= minimal) cover for F. Show, step by step, how the algorithm taught in class finds this minimal cover.
  2. Let X = { B , D }. Use the table algorithm to find X+F,AA.
  3. Find one elementary key of R, and one superkey of R that is not R. Prove your answer.
  1. Find a set of functional dependencies having two non-redundant covers, each one with a different number of dependencies.
  1. Consider changing the algorithm given in class for finding non-redundant covers (see also Ullman, Theorem 7.3), so that first redundant dependencies are removed, and afterwards redundant attributes are removed. Show that such an algorithm can produce redundant dependencies.
  1. For the (correct) algorithm for finding non-redundant covers, prove that it is sufficient to check each attribute and each dependency only once.