O'Reilly logo

Database Design and Relational Theory by C.J. Date

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required