The Databases Course

Exercise No. 7

Design Theory - Theoretical

Due on February 11th by midnight

  1. Let R = <S,F> , S = {A,B,C,D,E} and F = { AB ® C, BE ® A, C ® D, D ® B, DE ® A}.
  1. Find a non-redundant cover of F.
  2. Find all the simple keys of R.
  3. Categorize each dependency from your answer of (a) as a partial, transitive or full dependency.
  4. Give a 3NF, lossless and dependency preserving (with respect to F) decomposition of S.
  5. What are the projected dependencies for each of your schemes?
  1. Let R = <S,F> , S = {A,B,C,D} and F = { B ® A, C ® A, D ® BC}.
    Let p be the decomposition { AB, AC, BD }.
  1. Find the projected dependencies for each of the relation schemes of p.
  2. Does p preserve the given dependencies?
  3. Does p have a lossless join with respect to the given dependencies?
  1. Prove the following lemmas:
  1. Every relation whose schema has two fields is in BCNF.
  2. A relation R that has a single simple key is in BCNF if and only if it is in 3NF.
  3. If R is in 3NF, and every simple key of R has only one field, then R is in BCNF.
  1. Given is a schema S = (A, B, C) and an instance of it that contains the following tuples:
    r = { (1,2,3), (4,2,3), (5,3,3), (5,3,4), (1,2,4), (4,2,1) }
    Which of the following multi-valued dependencies are violated by r, and which are not?
  1. A ®® B
  2. BC ®® A
  3. B ®® C

 

Answering the above four questions gives a full grade of 100% for this exercise. Answering each of the following questions gives an extra 10%, up to a maximum grade of 24 out of 20 in this exercise.

  1. Finding dependencies:
  1. Consider a relation with a schema S = (A,B,C,D) and a non-redundant dependency set F that includes three dependencies: AB®C, B®D and another dependency. Can R be in BCNF? If so, with what third dependency?
  2. A relation with S = (A,B,C) is in 3NF but not in BCNF, and has a non-redundant dependency set F = { C ® B, X ® Y }. Find all the possibilities for X and Y.

 

  1. The following algorithm is suggested for the decomposition of R=<S,F>. We find an X®Y in F that violates BCNF, decompose S into S1 = S - Y and S2 = {X,Y}, and then active the algorithm recursively on S1 and S2. For example, if given S = <A,B,C,D,E> and F = { AB®C, B®D, C®E}, we first find that B®D violates BCNF (it's a partial dependency), so we create S1 = (ABCE) and S2=(BD). S2 is in BCNF because it only has two fields, but S1 is not in BCNF becuase of the dependency C®E. So again we create S3=(ABC) and S4=(CE). Now both S3 and S4 are in BCNF, so we conclude to say that our final answer is p = { BD, ABC, CE }.
  1. Prove that this algorithm returns a lossless decomposition that is in BCNF.
  2. Show an example that shows that the algorithm may return a non-dependency-preserving decomposition.

 

Before the test, be sure to review the following questions from last year:

Exercise 6, question 4.

Exercise 8, questions 4 and 5.