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:

{ { 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 ...

Start Free Trial

No credit card required