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:
