The Databases Course

Exercise No. 8

More Design Theory

Due on January 15th by midnight

1. Let R = <S,F> , S = {A,B,C,D} and F = { AB ® C , A ® D , BD ® C }.

1. Find a non-redundant cover of F.
2. Give a 3NF, dependency preserving (with respect to F) decomposition of S into only two schemes.
3. What are the projected dependencies for each of your schemes?
4. Does your answer to (b) have a lossless join? If not, how could you modify the database scheme to have a lossless join and still preserve dependencies?

2. Let R = <S,F> , S = {A,B,C,D} and F = { A ® B , B ® C , A ® D , D ® C }.
   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?

3. You are given a relation scheme S = { A₁, ..., A_n } and a set of functional dependencies F. Write an algorithm which computes a simple key of R = <S,F>. Your algorithm should be as simple and as efficient as possible. What is the running time of your algorithm?

4. The algorithm that was taught in class and checks whether a given decomposition has a lossless join, includes the clause "if V_ij = b_ij and V_mj = b_mj then V_ij = V_mj" - that is, copy 'b_ij' and not only 'a_i' between lines while trying to build a full line of 'a_i'. Prove that this clause is necessary, but giving an example scheme and decomposition that demonstrate this point.

5. For each of the following statements, prove that it's true or give a counter example to show that it isn't:

1. X ® Y |- X ®® Y
2. X ®® Y |- X ®® (S - XY)
3. X ®® Y , Y ®® Z |- X ®® Z