Databases Reference

In-Depth Information

{ S , M }
→
{ R }

{ M }
→
{ D , Y }

{ S }
→
{ B }

{ B }
→
{ Z , C }

{ Z , C }
→
{ H }

{S,M} is a key. The BCNF procedure yields {S,M,R}, {M,D,Y}, {S,B}, {B,Z,C}, and {Z,C,H}. No FDs

are lost.

CHAPTER 7

7.1

See the body of the chapter.

7.2 The closure
F
+
of a set
F
of FDs is the set of all FDs implied by those in
F
. The closure of the set of FDs that

hold in the shipments relvar SP is given in the answer to Exercise 4.1.

7.3 The FD
X
→
Y
is satisfied if and only if whenever two tuples agree on
X
, they also agree on
Y
(I'm

deliberately giving this definition in a pretty loose form). So:

If two tuples agree on
X
, they certainly agree on every subset
Y
of
X
, so the reflexivity rule is reasonable.

If two tuples agree on
XZ
, they certainly agree on
Z
. They also certainly agree on
X
and hence, if
X
→
Y
is

satisfied, on
Y
as well; hence they agree on
YZ
, and so the augmentation rule is reasonable.

If two tuples agree on
X
and
X
→
Y
is satisfied, they agree on
Y
. If they agree on
Y
and
Y
→
Z
is satisfied,

they agree on
Z
. So the transitivity rule is reasonable.

7.4

See the body of the chapter.

7.5

Let
U
denote the intersection of
Z
and
Y
and let
V
denote the difference
Z - Y
between
Z
and
Y
(in that order).

Then:

1.

X
→
Y
(given)

2.

Z
→
W
(given)

3.

X
→
U
(1, decomposition)

4.

XV
→
UV
(3, augmentation)

5.

XV
→
Z
(simplifying 4)

6.

XV
→
W
(5, 2, transitivity)

7.

XV
→
YW
(1, 6, composition; this completes the proof)

The rules used in this proof are indicated in the comments. The following rules are all special cases of

Darwen's theorem: the union, transitivity, and augmentation rules. So too is the following useful rule:

If
X
→
Y
and
XY
→
Z
, then
X
→
Z
.

Note:
This latter is a special case of what's sometimes called the
pseudotransitivity
rule, which in its general form

looks like this: