Databases Reference
In-Depth Information
normalization, which is what we're supposed to be talking about, isn't a matter of decomposing relations, it's a matter of
decomposing
relvars
.
These remarks apply here too! So let's get back to relvars ... Consider relvar S once again. Suppose we do
decide to perform the recommended decomposition into “projection” relvars SNC and CT; moreover, suppose we
want that decomposition to be nonloss, as indeed we surely do. In other words, what we want is for the
decomposition to be such that,
at all times
, the current value of relvar S is equal to the join of the current values of
SNC and CT.
6
That is, we want S to be subject to the following integrity constraint (I'll call it YCT):
CONSTRAINT YCT
S = JOIN { S { SNO , SNAME , CITY } , S { CITY , STATUS } } ;
Now, recall from Chapter 2 that S is certainly subject to the following constraint (XCT):
CONSTRAINT XCT
COUNT ( S { CITY } ) = COUNT ( S { CITY , STATUS } ) ;
Just to remind you, this constraint merely says the FD {CITY} → {STATUS} holds in S. Appealing to Heath's
Theorem, therefore, we see that every possible value of relvar S, since it necessarily satisfies constraint XCT,
certainly satisfies constraint YCT as well. And it follows that constraint XCT
implies
constraint YCT (meaning, to
spell the point out, that if relvar S is subject to XCT—which it is—then it's certainly subject to YCT as well). So
constraint YCT does hold, and the decomposition of relvar S into relvars SNC and CT is indeed nonloss, as
required. It follows that we can take Heath's Theorem as applying to relvars after all, not just to relations. So let's
restate it accordingly:
Heath's Theorem
(
for relvars
): Let relvar
R
have heading
H
and let
X
,
Y
, and
Z
be subsets of
H
such that
the union of
X
,
Y
, and
Z
is equal to
H
. Let
XY
denote the union of
X
and
Y
, and similarly for
XZ
. If
R
is
subject to the FD
X
→
Y
, then
R
can be nonloss decomposed into its projections on
XY
and
XZ
.
There's one further point I want to make on the general topic of nonloss decomposition (to BCNF or
otherwise). Once again consider relvar S, with its FD {CITY} → {STATUS}. By Heath's Theorem, that relvar can
be nonloss decomposed into its projections on {SNO,SNAME,CITY} and {CITY,STATUS}. However, it can
clearly also be nonloss decomposed into those two projections
together with
(say) the projection on
{SNAME,STATUS}; that is, if we join all three of those projections together, we get back to where we started.
(Check this claim for yourself, using our usual sample value for relvar S, if it isn't immediately obvious.) However,
that third projection clearly isn't needed in the process of reconstructing the original relvar. Now, when we're doing
database design, for obvious reasons we usually consider only decompositions for which every projection
is
needed
in the reconstruction process—but in this topic I'm discussing decompositions in general, and I won't limit myself
to those for which every projection is needed (barring explicit statements to the contrary, of course).
EXERCISES
5.1 The version of join defined in the body of the chapter is an
n-
adic operator, not just a dyadic one. But what
happens if
n
= 1? Or
n
= 0?
6
Here I'm adopting the convenient fiction again that relvars S, SNC, and CT all coexist (living alongside one another, as it were).
