Closure of a Set of Functional Dependencies
- We need to consider all functional dependencies that hold. Given a set F of functional dependencies, we can prove that certain other ones also hold. We say these ones are logically implied by F.
- Suppose we are given a relation scheme R=(A,B,C,G,H,I), and the set of functional dependencies:
Then the functional dependency is logically implied.
- To see why, let and be tuples such that
As we are given A B , it follows that we must also have
Further, since we also have B H , we must also have
Thus, whenever two tuples have the same value on A, they must also have the same value on H, and we can say that A H .
- The closure of a set F of functional dependencies is the set of all functional dependencies logically implied by F.
- We denote the closure of F by .
- To compute , we can use some rules of inference called Armstrong’s Axioms:
- Reflexivity rule: if is a set of attributes and , then holds.
- Augmentation rule: if holds, and is a set of attributes, then holds.
- Transitivity rule: if holds, and holds, then holds.
- These rules are sound because they do not generate any incorrect functional dependencies. They are also complete as they generate all of .
- To make life easier we can use some additional rules, derivable from Armstrong’s Axioms:
- Union rule: if and , then holds.
- Decomposition rule: if holds, then and both hold.
- Pseudotransitivity rule: if holds, and holds, then holds.
- Applying these rules to the scheme and set F mentioned above, we can derive the following:
- A H, as we saw by the transitivity rule.
- CG HI by the union rule.
- AG I by several steps:
- Note that A C holds.
- Then AG CG , by the augmentation rule.
- Now by transitivity, AG I .