Microsoft Word – hw4.doc
Assignment 4
Relational Design theory
Prof. Brodsky – Database Management
Problem 1. Given a relation schema R(A,B,C) and its relation instance as follows:
A B C
1 2 3
4 2 5
6 2 3
6 2 5
7 8 9
7 8 5
Answer: Which of the following functional dependencies are satisfied by the above
relation instance. If the dependency is not satisfied, explain why by specifying the tuples
(i.e., the counterexample) that cause the violation:
1. AB->C
2. A->B
3. C->A
4. BC->A
5. ABC->A
6. AB->AC
Problem 2. Consider relation schema R(A,B,C) and the set of functional dependencies:
F= { B->A, A->C }. Do the following:
1. Find the cover of F, i.e., the set of all non-trivial fd’s implied by F with a single
attribute on the right and a minimal left hand side.
2. Find a non-empty instance of R (i.e., give a number of rows) that satisfies every
FD in F.
3. Find an instance of R that satisfies every FD in F, but not A->B.
4. Can you find an instance that satisfies every FD in F, but does not satisfy the FD
AB->C? If yes, give the instance. If not, explain why.
Problem 3. Consider the two following set of functional dependencies: F= { B -> CE, E –
> D, E -> CD, B -> CE, B -> A, } and G = { E -> CD, B -> AE }. Answer: Are they
equivalent? Explain your answer.
Problem 4. Consider the following relation schema R(A,B,C,D,E,F,G,H,I,J) and the set
of functional dependencies F= { A -> DE, IJ -> H, I -> A, J -> FG, G -> BC }. Is R in
BCNF? Justify your answer.
Problem 5. Consider a relation schema R(A,B,C,D,E) with the FD’s F = {C -> E, D ->
BC, E -> D, B -> A and A -> D}. This relation is in BCNF.
1. Explain why it is in BCNF
2. Now, suppose you decompose R into relations S(C,D,E) and T(A,B,D). Is this a
lossless join decomposition?
3. Give the set F1 of all FDs from the cover of F for schema S;
4. Give the set F2 of all FDs from the cover of F for schema T
5. Does F1 union F2 logically imply F?
Problem 6. Consider the following relational schema R(A,B,C,D,E,F) with the following
functional dependencies: AC -> F, B -> D, AB -> CEF, ACE -> B, and AEF -> BC
Do the following:
1. Give all the candidate keys for relation schema R(A,B,C,D,E,F) (under the set
semantics).
2. Is relation R in BCNF? If not, show which FD violates the BCNF condition and
explain why.
3. Apply the BCNF decomposition algorithm