So how do we determine whether a given nontrivial JD is implied by keys? It turns out there’s an algorithm, the membership algorithm (due to Fagin), that does the job. It works like this. Let relvar R have heading H, and let 
{X1,...,Xn} be a JD, J say, with respect to H. Then:
If two distinct components of J both include the same key K of R, replace them in J by their union.
Repeat the previous step until no further replacements are possible.
Then the original JD is implied by the keys of R if and only if J is now trivial—i.e., if and only if the final version of J contains H as a component.[102] (Notice, incidentally, that trivial JDs in particular cause the algorithm to succeed, trivially.)
Let’s look at a few examples. First of all, consider our usual suppliers relvar S. Here’s another JD—let’s call it J1—that holds in that relvar:
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:
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:
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:
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:
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 key {A} considered in isolation. No. 4 would be implied by keys—actually by an individual key—if and only if {C} were a key, but it isn’t; what’s more, that JD can’t possibly hold in R, because if it did, then {C} would have to be a key after all (think about it!). As for No. 5, it clearly isn’t implied by the keys; it might or might not hold in R, but if it does, then R can’t be in 5NF.
So what exactly is going on in these examples? Let me try to explain the intuition behind what I’ve been saying (you might like to try interpreting what follows in terms of the suppliers relvar S and the JD {{SNO,SNAME},{SNO,STATUS},{SNAME,CITY}}, under the assumption once again that {SNO} and {SNAME} are both keys for that relvar):
Let X1, ..., Xn be subsets of the heading H of relvar R, such that the union of X1, ..., Xn is equal to H.
Let J be the JD
{X1,...,Xn}, and let J be implied by the keys of R.Let r be the relation that’s the current value of R.
Choose, arbitrarily, two distinct elements (components) of the set {X1,...,Xn}, say X1 and X2.
Let r1 and r2 be the projections of r on X1 and X2, respectively.
Now, if X1 and X2 both include the same key K of R, then the join r12 of r1 and r2—whose heading X12 will be the union of X1 and X2—will be a strict one to one join, and so r1 and r2 can be replaced by r12 without loss of information. (At the same time, X1 and X2 can be replaced in J by X12.) Since the original version of J was implied by the keys of R, performing such replacements repeatedly will, by definition, eventually yield a relation (a) that’s equal to the original relation r, and in particular (b) will therefore have a heading equal to the entire heading H.
Let me now point out that everything I’ve said so far becomes much simpler in the common special case where the pertinent relvar R has just one key K. In that case, the JD {X1,...,Xn} is implied by keys if and only if both of the following are true:
Every attribute of R is included in at least one of X1, ..., Xn. (This requirement always applies, of course, in the general case as well as in this special case.)
The sole key K of R is included in each of X1, ..., Xn—in other words, each of X1, ..., Xn is a superkey.
So if R has just one key K, then R is in 5NF if and only if every component of every JD that holds in R includes that key K.[103] (However, please note that—important!—I’m assuming here that the only JDs under consideration are ones that are irreducible with respect to R. See Chapter 11.) By way of example, consider the parts relvar P. The only irreducible JDs {X1,...,Xn} that hold in that relvar are such that each Xi (i = 1, ..., n) includes the sole key {PNO}. Those JDs are clearly all implied by that sole key, therefore, and relvar P is in 5NF. Here’s one of the JDs in question:
Thus, relvar P can be nonloss decomposed into its projections on the components of this JD. Whether we would actually want to perform that decomposition is another matter, of course. We know we could if we wanted to, that’s all.
Let me close this section by revisiting the SPJ example from Chapter 9. For convenience, a sample value of that relvar is shown in Figure 10-1 (a repeat of Figure 9-1). The predicate is Supplier SNO supplies part PNO to project JNO, and the following business rule is in effect:
If supplier s supplies part p and part p is supplied to project j and project j is supplied by supplier s, then supplier s supplies part p to project j.
Now, we know from Chapter 9 that (as I put it in that chapter) the following JD captures the essence of this business rule and so holds in SPJ:
Now we can see this JD isn’t implied by the sole key (viz., {SNO,PNO,JNO}) of the relvar, because the membership algorithm fails, and so SPJ isn’t in 5NF. So it can be nonloss decomposed into its three binary projections, and probably should be, if we want to reduce redundancy. Those three projections are all in 5NF (no JDs hold in them at all apart from trivial ones).
[102] In practice, of course, we might not need to go all the way to the bitter end and compute that final version of J—we can quit as soon as a component is produced that’s equal to H.
[103] Note that this isn’t the case with relvar S—that relvar is subject to at least one JD for which at least one component fails to include the sole key {SNO} (viz., {{SNO,SNAME,CITY},{CITY,STATUS}}) and so isn’t in 5NF.