Databases Reference

In-Depth Information

If
X
→
Y
and
YW
→
Z
, then
XW
→
Z
.

7.6

The first step is to rewrite the given set of FDs such that every FD has a singleton right side:

1.
AB
→
C

2.
C
→
A

3.
BC
→
D

4.
ACD
→
B

5.
BE
→
C

6.
CE
→
A

7.
CE
→
F

8.
CF
→
B

9.
CF
→
D

10.
D
→
E

11.
D
→
F

Now:

2 implies 6, so we can drop 6.

8 implies
CF
→
BC
by augmentation, which with 3 implies
CF
→
D
by transitivity, so we can drop 9.

8 implies
ACF
→
AB
by augmentation, and 11 implies
ACD
→
ACF
by augmentation, and so
ACD
→
AB
by

transitivity, and so
ACD
→
B
by decomposition, so we can drop 4.

No further reductions are possible, and so we're left with the following irreducible cover:

AB
→
C

C
→
A

BC
→
D

BE
→
C

CE
→
F

CF
→
B

D
→
E

D
→
F

Alternatively:

2 implies 6, so we can drop 6 (as before).

2 implies
CD
→
AD
by augmentation, which implies
CD
→
ACD
by augmentation again, which with 4

implies
CD
→
B
by transitivity, so we can replace 4 by
CD
→
B
.

2 and 9 imply
CF
→
AD
by composition, which implies
CF
→
ADC
by augmentation, which with (the

original) 4 implies
CF
→
B
by transitivity, so we can drop 8.

No further reductions are possible, and so we're left with the following irreducible cover: