# Closure of a Set of Functional Dependencies

## 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:*A B**A C**CG H**CG I**B H*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 haveFurther, since we also have

*B H*, we must also haveThus, 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*.

- Note that