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.
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.
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).
Search WWH ::

Custom Search