1. Make sure ALL dependencies have singleton right hand sides
a. Using decomposition, split all FDs so that there is only one attribute on the right hand side
2. Remove extraneous attributes on the left hand side
a. Look for FDs that have 2 or more attributes on the LHS
b. Compute closure of attributes for EACH of those attributes
i.
Do NOT include that FD when you compute the closure for those attributes
c. An attribute is extraneous if
i. It appears in the closure of any of the other attributes on the LHS
OR
ii. The closure of the any of the other attributes on the LHS determines the RHS without using that attribute
d. If the attribute is extraneous, remove it from the LHS of that FD
e. Do ONE FD at a time
3. Remove redundant FDs from those that are remaining
a. Compute the closure on all the attributes on the left hand side
i. Do NOT include that FD when you compute the closure for those attributes
b. If the attribute on the right hand side of that FD appears in the closure, that FD is redundant
i. Remove it from the FD
c. Do ONE FD at a time
R(A,B,C,D,E)
F= { A->D, BC->AD, C->B, E->A, E->D }
1. Make sure ALL dependencies have singleton right hand sides
a. Split BC->AD into BC->A and BC->D
F= { A->D, BC->A, BC->D, C->B, E->A, E->D }
2. Remove extraneous attributes on the left hand side
a. Compute a+ for each dependency
i. If b is in the set, that FD is not needed
B+ is B
C+ is CBAD
B is included in C+, so it is extraneous in BC->A
Replace BC->A with C->A in the set
New set of FDs becomes:
F= { A->D, C->A, BC->D, C->B, E->A, E->D }
BC->D – temporarily remove this dependency from the set
B+ is B
C+ is CADB
B is included in C+, so it is extraneous in BC->D –
BC->D becomes C->D
New set of FDs becomes:
F= { A->D, C->A, C->D, C->B, E->A, E->D }
3. Remove redundant FDs
A->D – temporarily remove this dependency from the set
A+ is A
Not redundant
F= { A->D, C->A, C->D, C->B, E->A, E->D }
C->A
C+ is CDB
Not redundant
C->D
C+ is CADB
Redundant - eliminate
F= { A->D, C->A, C->B, E->A, E->D }
C->B
C+ is CAD
Keep
E->AD
E+ is ED
Keep
E->D
E+ is EAD
F= { A->D, C->A, C->B, E->A }