Databases Reference
In-Depth Information
that (a) every JD that holds in
R
is equivalent to some irreducible JD that holds in
R
(as previously stated, in
fact), and hence that (b) the irreducible JDs that hold in
R
in fact imply all of the JDs that hold in
R
.
If some component
Xi
is irrelevant in
J
, then
J
is certainly reducible with respect to every relvar in which it
holds (because
Xi
can be dropped without significant loss). However,
J
can still be reducible with respect to
some relvar even if all components are relevant, as I now show.
Consider the suppliers relvar S once again. For simplicity, however, let's agree to ignore attribute SNAME;
what's more, let's agree to take the name “S” to refer to this reduced version of the relvar, until further notice. Now
consider the following JD:
{ { SNO , CITY } , { CITY , STATUS } , { SNO , STATUS } }
This JD─let's call it J1─has no irrelevant components. However, I'll show that (a) it holds in relvar S but (b) it's
reducible with respect to that relvar, because the {CITY,STATUS} component can be dropped and what's left is
still a JD of S.
Note:
Actually the reducibility in this example is intuitively obvious, because (to state the matter
precisely) the projection on {CITY,STATUS} of S is clearly equal to the projection on {CITY,STATUS} of the join
of S{SNO,CITY} and S{SNO,STATUS}. As a consequence, the {CITY,STATUS} component adds nothing, as it
were. To repeat, therefore: The reducibility is “obvious”─but now I want to
prove
it.
a.
First, then, suppose the following tuples appear in S (simplified notation for tuples;
s1
and
s2
denote supplier
numbers,
c1
and
c2
denote supplier cities, and
t1
and
t2
denote status values):
2
s1 c1 t2
s1 c2 t1
s2 c1 t1
Because {SNO} is a key, the following FDs hold in S:
{ SNO }
→
{ CITY }
{ SNO }
→
{ STATUS }
We can therefore conclude that
c1
=
c2
and
t1
=
t2
, and so the tuple
s1 c1 t1
appears in S, necessarily, because in fact it's identical to the first (or, equally, the second) in the original list
of tuples as shown above. But to say the original “three” tuples cause this “fourth” tuple to appear─if you
see what I mean─is to say, precisely, that JD J1 holds (i.e., that's what J1 says). So J1 does hold in S.
b.
Now appealing to either of the FDs {SNO} → {CITY} and {SNO} → {STATUS} (both of which hold in
S, as we know) and to Heath's Theorem, we see that the following JD─let's call it J2─certainly holds in
relvar S:
{ { SNO , CITY } , { SNO , STATUS } }
2
Note how each of these tuples corresponds to one component of the given JD (J1).
