CS550 Assignment 4-Relational Design Theory Solution

Relational Design Theory
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

Which of the following functional dependencies are satisfied by the above relation instance? Give a “yes” or “no” answer for each.

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 FDs implied by F with a single attribute on the right and a minimal left-hand side.
2. Does there exist an instance that satisfies every FD in F, but does not satisfy the FD AB->C? Give a “yes” or “no” answer.

Problem 3. Consider the two following sets of functional dependencies: F= { B -> CE, E -> D, E -> CD, B -> CE, B -> A, } and G = { E -> CD, B -> AE }.

Answer: Are they equivalent? Give a “yes” or “no” 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 }. Answer the following:

1. Is R in BCNF? Give a “yes” or “no” answer.
2. Find all candidate keys of R given a set F of functional dependencies.
3. Is R in 3NF? Give a “yes” or “no” 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}.

1. Is (R,F) in BCNF? Give a “yes” or “no” answer.
2. Now, suppose you decompose R into schemas S(C,D,E) and T(A,B,D). Is this a lossless join decomposition? Give a “yes” or “no” answer.
3. Give the cover of F for schema S (i.e., FDs from the cover involving only C,D and E).
4. Give the cover of F for schema T (i.e., FDs from the cover involving only A,B and D).
5. Does this decomposition preserve dependencies? Give a “yes” or “no” answer.

Problem 6. Consider the following relational schema R(A,B,C,D,E,F) with the following functional dependencies cover: cover(F) =

{ B  D, AB  C, AB E, AB F, AC F, ACE  B, ACE  D, AEF  B, AEF  C, AEF  D }


Do the following:

1. Give the set of all candidate keys for relation schema R(A,B,C,D,E,F).
2. Is (R,F) in the 3rd Normal Form? Give a “yes” or “no” answer.
3. Give the set of all FDs in cover(F) that violate the 3NF condition. Note, that if none exist (i.e., it is in 3rd normal form), your answer set should be empty.
4. Is (R,F) in BCNF? Give a “yes” or “no” answer.
5. Give the set of all FDs in cover(F) that violate the BCNF condition, if any. Note that if none exist (i.e., it is in BCNF), your answer set should be the empty set.
6. Decompose the relation schema R into several relational schemas in BCNF using the decomposition algorithm. Show each step of the decomposition algorithm,
i.e., an FD from cover(F) being used to decompose and the two resulting schemas. For the purpose of grading:
• always use the LEFTMOST FD in cover(F) (in the order it is written) that can be used to decompose a schema at each step of the algorithm.
• Write each schema as a string sorted in alphabetical order (e.g., “ABDF”, “BDF” or “ACF”)