Armstrong’s Axioms) [16 points]
[6 points] Let R(A,B,C,D,E) be a relation schema, and let F={A→BC,CD→E,B→D,E→A} be a set of functional dependencies (FDs). Show for each of the following FDs whether they can be logically implied from F by using Armstrong’s axioms and their derived inference rules. Show each step.
- [3 points] BC→AE
- [3 points] A→E
- [5 points] Let R(A,B,C,D,E,F) be a relation schema, and let F ={AB→E,AC →F,BEF →D} be a set of functional dependencies (FDs). Which of the following attribute sets is a candidate key? Explain your answer by using Armstrong’s axioms and their derived inference rules.
- BEF
- ABC
- DE
- [5 points] Let R(A,B,C,D,E,F) be a relation schema, and let F = {AB → C,BC → DE,AC → E,DE →F} be a set of functional dependencies (FDs). Infer at least five new FDs by using Armstrong’s axioms and their derived inference rules. All rules in your answer should be different.
2
Closure) [37 points]
[10 points] Consider the relation schema R(A,B,C,D,E,F) with the functional dependencies F =
{A→B,AB→C,BC→DE,AC→E,DE→F} and G={A→BC,B→CDE,C→E,D→BCE,E→
D}.
- [5 points] Determine if the two sets F and G are equivalent or not. Explain your answer in detail.
- [5 points] Determine if AB is a candidate key of R with respect to F.
- [6 points] Consider the relation schema R(A,B,C,D,E) with the functional dependencies F={A→ C,B→D,BD→E,C →E}. Which of the following sets of attributes functionally determine CD? Show each step.
- BC
- BD
- AE
- [6 points] Consider the relation schema R(A,B,C,D) with the functional dependencies F ={AB→ C,C→D,B→C}. We state that the FD C→B cannot be logically implied by the given F.
- [3 points] Prove why C→B cannot be logically implied.
- [3 points] Provide an example for your answer. (For the example, you can provide a table that has tuples with some values in it.)
- [6 points] Let R(A,B,C,D,E,F) be a relation schema, and let F={AB→D,CE→F,AC→DE,BD→ CF} be a set of functional dependencies (FDs). Which of the following attribute sets is a candidate key?
- BD
- AC
- AB
- [4 points] Consider the relation schema R(A,B,C,D,E,F) with the functional dependencies F={A→ B,CD→E,B→D,C→A}. By using the algorithm for calculating attribute closures provided in the lecture slides, calculate the closure of the following attribute set. Show each step.
- CE
- [5 points] Let R(A,B,C) be a relation schema, and let F={A→B} be a set of functional dependencies (FDs). Write down all the functional dependencies of the closure F+ of F and count them. Use the exponential algorithm from the lecture for calculating the closure of functional dependencies.
3
Minimal Cover) [32 points]
[10 points] Find a minimal cover for the relation schema R(A,B,C,D,E,F) with the set F ={A→ B,AB→C,BC→DE,AC→E,DE→F} of functional dependencies. Show each step.
- [10 points] Find a minimal cover in a standard form for the relation schema R(A,B,C,D,E) with the set F ={A→BC,B→CDE,C →E,AD→BCE,E →D} of functional dependencies. Show each step.
- [12 points] Find a minimal cover for the relation schema R(A,B,C,D,E,F,G) with the set F={AB→ C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→G} of functional dependencies.
Show each step.
4
Candidate Keys) [15 points]
[9 points] Consider the relation schema R(A,B,C,D,E,F,G,H) with the set F = {B → CE,E → FH,BC→H,CD→A,A→DG,H →BCE,H →G} of functional dependencies. List all candidate keys of R in a systematic manner (do not use Armstrong’s axioms) and explain how you determine them. Show each step.
(b) [6 points] Consider the relation schema R(A,B,C,D,E,F) with the set F ={AB→C,CD→F,F→ A,CE→D} of functional dependencies. List all candidate keys of R in a systematic manner (do not use Armstrong’s axioms) and explain how you determine them. Show each step.
5
