So far the notion of one JD implying another has been more or less syntactic in nature—I haven’t really paid much attention to the question of whether the JDs we’re talking about actually hold in some given relvar. (Observe that neither the definition of irrelevant components, nor the theorem about replacing components by their union, made any mention of a relvar, nor even of a heading.) Now, however, let’s consider JDs that do actually hold in some relvar. Then we have the following theorem:
Theorem: Let JD J hold in relvar R; then J is equivalent to some irreducible JD (not necessarily unique) that also holds in R. Note, however, that equivalence here has to be understood in the context of some particular relvar; it’s possible for two JDs both to hold in one relvar and not both to hold in another. In such a case, the two JDs might or might not be equivalent with respect to the first relvar, but they’re certainly not equivalent with respect to the second.
I’ll explain exactly what it means for a JD to be irreducible in a moment. Before I do, however, let me just remind you of a parallel with the world of FDs. Recall from Part II of this book that every FD that holds in relvar R implies some irreducible FD that also holds in relvar R. (This is easy to see: Just keep dropping attributes from the determinant until what remains is an FD that no longer holds.) Similarly, every JD that holds in relvar R implies—in fact, is equivalent to (a stronger statement)—some irreducible JD that also holds in relvar R.
So what does it mean for a JD to be irreducible? Here’s a definition:
Points arising:
It’s easy to see that every JD that holds in relvar R implies an irreducible JD that also holds in relvar R—just keep dropping components from the given JD until what’s left is a JD that no longer holds in R, and then the last one that does hold is irreducible.
It’s also easy to see that the implication goes the other way, too: Start with the irreducible JD and add the dropped components back in until the original JD is reached. At each step in this process, the current version of the JD will be a JD that holds in R. Note: From this point and the previous point taken together, it follows 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):[106]
s1 c1 t2s1 c2 t1s2 c1 t1Because {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 t1appears 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 } }But the components of J2 form a proper subset of those of J1. It follows that J1 is reducible with respect to S. To be specific, the component {CITY,STATUS} can be dropped from J1 without loss, in the sense that what remains is still a JD of S.
Observe now that the foregoing proof made no use of the fact that the FD {CITY} → {STATUS} holds in S (indeed, the result would still be valid even if that FD didn’t hold). But now let’s do another example that does make use of that FD:
First, we know now that the following JD (J1 from the previous example) holds in S:
{ { SNO , CITY } , { CITY , STATUS } , { SNO , STATUS } }But the FD {CITY} → {STATUS} also holds, and so by Heath’s Theorem the following JD—let’s call it J3—holds as well:
{ { CITY , STATUS } , { CITY , SNO } }The components of J3 form a proper subset of those of J1, and so it follows once again that J1 is reducible with respect to S. To be specific, the component {SNO,STATUS} can be dropped from J1 without loss, in the sense that what remains is still a JD of S.
Observe, therefore, that the original JD J1 is equivalent, with respect to relvar S, to two distinct JDs: namely, J2 and J3.
In general, of course, the question is: Given relvar R and a JD J that holds in R, how can we find an irreducible equivalent (meaning, to be more precise about the matter, a JD that’s both equivalent to J and irreducible, where equivalent and irreducible are both understood as being with respect to R)? Well:
If some component is irrelevant in J, that component can clearly be dropped.
If all components are relevant, we can only try dropping one, and then:
If what’s left is still a JD of R, we drop another component and repeat the process.
If what’s left isn’t a JD of R, we reinstate the dropped component and try dropping another one.
Eventually, we’ll arrive at a JD that’s equivalent to the original one and is irreducible.
And how do we tell whether some JD is in fact a JD of R? Well, if it’s one that’s been explicitly declared as such, there’s clearly no problem; but if not, we use the chase, which I’ll be describing in the next section but one.