## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# JDs IMPLIED BY KEYS

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:

1. If two distinct components of J both include the same key K of R, replace them in J by their union.

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required