Homework 4.1
Question 1 (Functional Dependencies − Armstrong’s Axioms) [16 points] (a) [6 points] Let R(A,B,C,D,E,F) be a relation schema, and let F = {AC→ B,BD→ F,F→ CE} 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. (1) [4 points] ACF→ BE (2) [2 points] Explain why AB→ C cannot be implied from F . (b) [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 (c) [5 points] Let R(A,B,C,D,E,F) be a relation schema, and let F = {A→B,C→A,BD→C,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 Question 2 (Functional Dependencies − Closure) [37 points] (a) [10 points] Consider the relation schema R(A,B,C,D,E) with the functional dependencies F = {A→ B, AB→ C,D→ AE,C→ E} and G = {A→ BC,C→ E,D→ BC,E→ D}. (1) [5 points] Determine if the two sets F and G are equivalent or not. Explain your answer in detail. (2) [5 points] If a functional dependency E→ D is inserted into F , does it make your answer to (a) different? (b) [6 points] Consider the relation schema R(A,B,C,D,E) with the functional dependencies F = {AB→ C,C → D,BD→ E,D→ A}. Which of the following sets of attributes functionally determine E? Show each step. • AD • CD • BC (c) [6 points] Consider the relation schema R(A,B,C,D) with the functional dependencies F = {AB→ C,C→ B,D→ C}. We state that the FD C→ D cannot be logically implied by the given F . (1) [3 points] Prove why C→ D cannot be logically implied. (2) [3 points] Provide an example for your answer. (For the example, you can provide a table that has tuples with some values in it.) (d) [6 points] Let R(A,B,C,D,E,F,G,H) be a relation schema, and let F = {A → B,B → G,AC → D,DF→ E,FG→ BH} be a set of functional dependencies (FDs). Which of the following attribute sets is a candidate key? • ABCE • ACF • BDH (e) [4 points] Consider the relation schema R(A,B,C,D,E,F) with the functional dependencies F = {A→ BC,CD→ E,B→ D,E→ 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. • BE (f) [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 Question 3 (Functional Dependencies −Minimal Cover) [32 points] (a) [10 points] Find a minimal cover for the relation schema R(A,B,C,D,E) with the set F = {A→ BC,CD→ AE,ABD→ CD,CE→ AD} of functional dependencies. Show each step. (b) [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. (c) [10 points] Find a minimal cover in a standard form for the relation schema R(A,B,C,D,E,F,G,H) with the set F = {A→ BCD,AC→ EF,AG→H,CD→ FG} of functional dependencies. Show each step. 4 Question 4 (Functional Dependencies − Candidate Keys) [15 points] (a) [7 points] Consider the relation schema R(A,B,C,D,E,F,G,H, I,J) with the set F = {B→ E,E→ FH,BCD→ G,CD→ A,A→ J, I → BCDE,H → I} 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) [8 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