Databases Reference
In-Depth Information
Then the following procedure will produce an irreducible cover for this given set.
1.
First, rewrite the FDs such that each has a singleton right side:
A B
A C
B C
A B
AB C
AC D
Observe now that the FD A B occurs twice, so one occurrence can be dropped.
2.
Attribute C can be dropped from the left side of the FD AC D , because we have A C , so A AC by
augmentation, and we're given AC D , so A D by transitivity; thus the C on the left side of AC D is
redundant.
3.
The FD AB C can be dropped, because again we have A C , so AB CB by augmentation, so AB C
by decomposition.
4.
The FD A C is implied by the FDs A B and B C , so it can be dropped.
We're left with:
A B
B C
A D
This set is irreducible.
As promised, in this section I show how to derive Rules 4-7 from the original Rules 1-3.
4.
X X (“self determination”).
Proof: Immediate by reflexivity.
5.
If X Y and X Z , then X YZ (“union”).
Proof: X Y (given), hence X XY by augmentation; also X Z (given), hence XY YZ by
augmentation; hence X YZ by transitivity.
6.
If X Y and Z W , then XZ YW (“composition”).
Proof: X Y (given), hence XZ YZ by augmentation; likewise, Z W (given), hence YZ YW by
augmentation; hence XZ YW by transitivity.

Search WWH ::

Custom Search