1. 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.

2. Suppose we are given a relation scheme R = (A,B,C,G,H,I), and the set of functional dependencies:
A → B
A → C
CG → H
CG → I
B → H
Then the functional dependency A → H is logically implied.

3. To see why, let t1 and t2 be tuples such that
t1[A] = t2[A]
As we are given A → B , it follows that we must also have
t1[B] = t2[B]
Further, since we also have B → H , we must also have
t1[H] = t2[H]
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 .

4. The closure of a set F of functional dependencies is the set of all functional dependencies logically implied by F.

5. We denote the closure of F by F+.

6. To compute F+, we can use some rules of inference called Armstrong's Axioms:

• Reexivity 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.

7. These rules are sound because they do not generate any incorrect functional dependencies. They are also complete as they generate all of F+.

8. 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.

9. 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 .
  (You might notice that this is actually pseudotransivity if done in one step.)