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.
PROVING THE ADDITIONAL RULES
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.
