Exercise 11: Finding Keys Using Armstrong’s Axioms

Armstrong’s Axioms and rules for splitting and combining.

• Reflexivity: X ⊆ Y ⇒ Y → X
• Augmentation: X → Y ⇒ XZ → YZ ∀ Z
• Transitivity: X → Y ∧ Y → Z ⇒ X → Z
• Combining: X → Y ∧ X → Z ⇒ X → YZ
• Splitting: X → YZ ⇒ X → Y ⇒ X→ Z

Exercise 3.2.1 from the textbook.

Consider a relation with schema R(A,B,C,D) and FD’s { AB → C, C → D, D → A }.

a. What are all the nontrivial FD’s that follow from the given FD’s? You should restrict yourself to FD’s with single attributes on the right hand side.

b. What are all the keys of R?

c. What are all the superkeys for R that are not keys ?

Exercise 3.2.2.

Repeat the Exercise 3.2.1 for the following schemas and sets of FD’s:

1. S(A,B,C,D) with FD’s { A → B, B → C, B → D }.
2. T(A,B,C,D) with FD’s {AB → C, BC → D, CD → A, AD → B }.
3. U(A,B,C,D) with FD’s {A → B, B → C, C → D, D → A}