Consider the following inference rules: 1. If X Y and WY→ Z, then XWZ. 2. If XYZ and Z WV, then X→→→ YZV. 3. If X Y and Z CY, then X →→ Z. P1.1. Prove that the first inference rule is sound using only the Armstrong Axioms. P1.2. Prove that the second inference rule is sound directly from the definition of functional dependencies (without using any inference rules). P1.3. Prove that the third inference rule is sound.
1 Functional Dependencies
The Armstrong Axioms are sound, complete, and independent. They are not the only options for reasoning about functional dependencies, however. For example, we have seen the Union and Decomposition rules. Next, we will explorer some alternative options:
Problem 1.
Consider the following inference rules:
1. If X Y and WY→ Z, then XWZ.
2. If XYZ and Z WV, then X→→→ YZV.
3. If X Y and Z CY, then X →→ Z.
P1.1. Prove that the first inference rule is sound using only the Armstrong Axioms.
P1.2. Prove that the second inference rule is sound directly from the definition of functional dependencies (without using any inference rules).
P1.3. Prove that the third inference rule is sound.
P1.4. Are these inference rules complete? If so, then prove why. Otherwise, show why not.
HINT: You may assume that the Armstrong Axioms are complete.
P1.5. Are these inference rules independent? If so, then show why. Otherwise, show why not.
Problem 2.
Consider the following two inference rules:
1. Y→Y for all sets of attributes Y.
2. If XY, YZ, and a CB, then XB-Za
P2.1. Prove that these inference rules are sound.
P2.2. Are these inference rules complete? If so, then prove why. Otherwise, show why not.
HINT: You may assume that the Armstrong Axioms are complete. P2.3. Are these inference rules independent? If so, then show why. Otherwise, show why not.
2 Closure and minimal cover
Problem 3. Consider the relational schema r(A, B, C, D, E) and the following set of functional dependencies:
S=(A→CDE, BDEBD,CD,D→ AB, E→ B).
P3.1. Provide the attribute closure of set of attributes C (hence, C) and of set of attributes EA (hence, (EA)*)
with respect to . Explain your steps.
P3.2. Compute the closure *. Explain your steps. Based on the closure, indicate which attributes are superkeys and which attributes are keys.
HINT: A superkey is a set of attributes that determines all attributes from r. A key k is a superkey of minimal size (if we remove any attribute from k, it is no longer a key).
P3.3. Provide a minimal cover for 6. Explain your steps.
3 Multi-valued and inclusion dependencies
Problem 4. Consider the following dependencies for relational schemas R and S:
1. If ABC, then A→→→ B.
2. If ABCD and AB, then A→ CD.
3. If R[AB] S[CC], then R[A] < R[B].
4. If R[AB] S[CC], then A→→→ B. In the above, S[CC] refers to the relational schema S in which the column C is used twice.
P4.1. For each inference rule: Is the inference rule sound? If so, then prove that the rule is sound. Otherwise, provide a counterexample.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
