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.