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

A PROCEDURE THAT WORKS

Here now is a procedure that’s guaranteed to produce a decomposition in which all relvars are in 3NF (though not necessarily BCNF) and all FDs are preserved.[59] For convenience, I’ll refer to it in what follows as the 3NF procedure. The input is a relvar R and what’s called an irreducible cover, C say, for the FDs that hold in R. I’ll explain what an irreducible cover is in a few moments—by the way, there’s that word irreducible again—but let me state the procedure first:

  1. Let S be a set of headings. Initialize S to the empty set, {}.

  2. Let X be the left side (the determinant) of some FD in C; let the complete set of FDs in C with left side X be XY1, ..., XYn; and let the union of Y1, ... Yn be Y. Add the union of X and Y to S. Perform this step for each distinct X.

  3. Let U be the set of attributes of R not contained in any element of S. If U is nonempty, add U to S.

  4. If no element of S is a superkey for R, add some key K of R to S.

At the conclusion of this procedure, the elements of S are the headings of a set of 3NF relvars into which R can be nonloss decomposed without losing any FDs. Note in particular that the procedure makes no explicit mention of 2NF, not even as some kind of stepping stone.

So how does it work? Clearly, the notion of an irreducible cover is important. In order to explain that notion, let me first call out something I’ve appealed to several times already in passing: namely, the fact that some FDs imply others. As a simple example, the FDs ...

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