Databases Reference
In-Depth Information
{ { SNO , SNAME } , { SNO , STATUS } , { SNO , CITY } }
We already know this JD holds by repeated application of Heath's Theorem. However, observe now that the
components {SNO,SNAME} and {SNO,STATUS} both include the key {SNO}; applying the membership
algorithm, therefore, we can replace them by their union {SNO,SNAME,STATUS}. J1 now looks like this:
{ { SNO , SNAME , STATUS } , { SNO , CITY } }
Note that (a) this revised version of J1 is itself a JD with respect to the heading of relvar S, and also that (b) relvar S
is subject to it─two facts that together should give some insight as to what's going on with the algorithm (see further
explanation later).
Next, the components {SNO,SNAME,STATUS} and {SNO,CITY} of this latter JD both include the key
{SNO}, and so we can replace them by their union {SNO,SNAME,STATUS,CITY}, to obtain:
{ { SNO , SNAME , STATUS , CITY } }
This further revision of J1 is again a JD with respect to the heading of S. However, all it says is that relvar S
is equal to the “join” of its identity projection (recall from Exercise 5.1 that the join of a single relation
r
, JOIN {
r
},
is identically equal to
r
); in other words, that further revision of J1 simply says S can be “nonloss decomposed” into
its identity projection. But this observation is trivially true:
Any
relvar can always be “nonloss decomposed” into its
identity projection, as we saw in Chapter 6. Indeed, the JD is now formally trivial, since it contains a component
that's equal to the pertinent heading. It follows that JD J1 as originally stated is implied by the keys of relvar S.
By way of a counterexample, consider now the following JD─let's call it J2─which also holds in relvar S:
{ { SNO , SNAME , CITY } , { CITY , STATUS } }
Since the sole key, {SNO}, of the relvar is certainly not included in both components of this (binary) JD, the
membership algorithm has no effect on it. Thus, the output from that algorithm is equal to the input (i.e., to the
original JD J2, unchanged); no component of that output is equal to the entire heading, and so J2 isn't implied by
keys (and relvar S isn't in 5NF, therefore).
Finally, let's consider some more abstract examples. Let relvar
R
have attributes
A
,
B
,
C
,
D
,
E
, and
F
(only);
let
R
have keys {
A
}, {
B
}, and {
C
,
D
}, and no others; and let
AB
denote the set of attributes {
A
,
B
}, and similarly for
other attribute name combinations (“Heath notation”─see Chapter 7). Now consider the following JDs:
1.
{
AB
,
ACDE
,
BF
}
2.
{
ABC
,
ACD
,
BEF
}
3.
{
AB
,
AC
,
ADEF
}
4.
{
ABC
,
CDEF
}
5.
{
ABD
,
ACDE
,
DF
}
Applying the membership algorithm to these JDs, we find that Nos. 1-3 are implied by keys (and
R
is
therefore subject to them, necessarily), while Nos. 4-5 aren't. To elaborate briefly: Nos. 1 and 2 are both implied
by the pair of keys {
A
} and {
B
} taken together, but not by any individual key; by contrast, No. 3 is implied by the
