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:
Let S be a set of headings. Initialize S to the empty set, {}.
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 X → Y1, ..., X → Yn; 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.
Let U be the set of attributes of R not contained in any element of S. If U is nonempty, add U to S.
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 X → Y and Y → Z together imply the FD X → Z—by which I mean, if the first two FDs are satisfied by relation r, then the third one must be satisfied as well. Or, perhaps more to the point: If the first two hold in relvar R, then the third one must hold as well. We saw an illustration in the previous section, in relvar RX3, where the FDs {CLASS} → {CITY} and {CITY} → {STATUS} both held and so the FD {CLASS} → {STATUS} held as well.
So some FDs imply others. Given a set F of FDs, then, we can sensibly talk about a cover for F. Here’s the definition:
Definition: A cover for a set F of FDs is a set C of FDs such that every FD in F is implied by the FDs in C.
As a trivial example, let F be the set:
{ X → Y , Y → Z , X → Z }Then the following are both covers for F:
{ X → Y , Y → Z }
{ X → Y , Y → Z , X → Z }This example illustrates two points: First, covers aren’t unique, in general; second, any set of FDs is certainly a cover for itself, because among other things every FD implies itself. A third and more important point is the following: Enforcing the FDs in a cover C for a given set F will “automatically” enforce those in that set F. Thus, given some set F of FDs that need to be enforced, it’s sufficient to find some cover C for F and enforce the FDs in C instead. (In particular, it’s sufficient to enforce the FDs in an irreducible cover for F, as will quickly become clear.)
Now I can define what it means for a cover to be irreducible:
Definition: A cover C for a set F of FDs is irreducible if and only if it possesses all of the following properties:
Singleton dependant: Every FD in C has just one attribute on the right side.
Irreducible determinant: Every FD in C is itself irreducible. Note: I’m being a trifle sloppy here. Recall from Chapter 4 and Chapter 5 that FD irreducibility is defined only with respect to some relvar—but I haven’t said anything here about the FDs in F as holding in any relvar, and there’s thus no context that would allow us to talk legitimately about FDs being irreducible. What I mean, however, is that no attribute can be discarded from the left side without losing the property that C is a cover for F.
No redundant FDs: No FD can be discarded from C without losing the property that C is a cover for F.
The obvious question arises: Given some specific set of FDs, how can we find an irreducible cover for that set? I’ll answer this question properly in the next chapter. For now, let me just give an example—namely, an irreducible cover for the FDs that hold in our usual suppliers relvar S:
{ SNO } → { SNAME }
{ SNO } → { CITY }
{ CITY } → { STATUS }To elaborate briefly: It’s certainly the case that every FD that holds in S is implied by these three taken together, so these three certainly constitute a cover. Also, each of the three has a singleton dependant; no attribute can be dropped from any of the determinants; and none of the FDs can be discarded. It follows that the cover is in fact an irreducible one. By contrast, the following sets of FDs are covers for the FDs that hold in S but aren’t irreducible (in each case, why not?):
{ SNO } → { SNAME , CITY }
{ CITY } → { STATUS }
{ SNO , SNAME } → { CITY }
{ SNO } → { SNAME }
{ CITY } → { STATUS }
{ SNO } → { SNAME }
{ SNO } → { CITY }
{ CITY } → { STATUS }
{ SNO } → { STATUS }Now let’s get back to the 3NF procedure. In particular, let’s see how it works out for the SJT example.[60] Just to remind you, the relvar had attributes S, J, and T; keys {S,J} and {S,T}; and was subject to the FD {T} → {J}. So these FDs hold:
{ S , J } → { T }
{ S , T } → { J }
{ T } → { J }It’s easy to see, however, that the FD {S,T} → {J} is redundant here—in fact, I effectively assumed as much when I first discussed this example earlier in the chapter—and hence that the other two FDs together form an irreducible cover (which I’ll call C):
{ S , J } → { T }
{ T } → { J }Now we can apply the 3NF procedure. We start with an empty set of headings S. The second step does two things: It gathers together FDs in C that have the same left side—something that’s effectively already been done in the example—and then adds the sets (actually headings)
{ S , J , T }
{ T , J }to S. The third step has no effect, since every attribute of the original relvar is now contained in at least one element of S. The last step also has no effect, since the element {S,J,T} of S is a superkey for the original relvar. Overall, therefore, the 3NF procedure tells us that relvar S can be nonloss decomposed, in an FD preserving way, into its projections on {S,J,T} and {T,J}. Points arising:
The projection on {S,J,T} is of course identical to the original relvar!—in other words, it’s an identity projection (see the section immediately following this one), and there isn’t much decomposition, as such, going on here.
There doesn’t actually seem to be much point in maintaining the second relvar (i.e., the projection on {T,J}) as well as the original one, unless we want to be able to say that, e.g., Professor Black teaches Physics without there existing, at the same time, some student who’s actually being taught by Professor Black. If we don’t want this ability, we probably won’t want to maintain that second relvar. Thus, the decomposition produced by the 3NF isn’t necessarily a recommended one—but, to repeat, it’s one in which all relvars are in 3NF and all FDs are preserved.
I’ll leave it as an exercise (Exercise 6.3) to show what happens when the 3NF procedure is applied to relvars RX1, RX2, and RX3. Meanwhile, I’d like to close this section with a few words regarding BCNF. First, we can add another (fifth) step to the 3NF procedure, as follows:
5. Let Z be an element of S such that the projection P of relvar R on the attributes of Z is not in BCNF; let X → Y be an element of C (i.e., an FD) that holds in P; and let X not be a superkey for P. Replace Z in S by (a) the union of X and Y and (b) the difference Z - Y between Z and Y (in that order). Perform this step for each distinct Z and each distinct X.
Now, the 3NF procedure applied to relvar SJT produced a set S consisting of the headings {T,J} and {S,J,T}. The projection of SJT on {T,J} is in BCNF, but the (identity) projection of SJT on {S,J,T} isn’t, because the FD {T} → {J} holds in this latter projection and {T} isn’t a superkey. Applying Step 5, therefore, we delete the heading {S,J,T} and insert (a) the union of {T} and {J}—but this insertion has no effect, since that union is already an element of S—and (b) the difference between {S,J,T} and {J}, in that order. Thus, S winds up with the following headings as elements:
{ S , T }
{ T , J }These are the headings of a set of BCNF relvars into which SJT can be nonloss decomposed (the keys for those relvars are {S,T} and {T}, respectively). As you can see, therefore, adding Step 5 to the 3NF procedure converts it into a BCNF procedure, though without any guarantee that FDs will be preserved. (In fact, of course, it’s impossible to provide any such guarantee, since we already know that BCNF and FD preservation can be conflicting objectives.) However, any FDs lost are ones that can’t be preserved without violating BCNF.
Actually we can simplify matters somewhat and go straight to BCNF—i.e., bypassing 3NF—as follows (the input is as for the 3NF procedure; i.e., it consists of a relvar R and an irreducible cover C for the FDs that hold in R):
Initialize S to contain just the heading of R.
(Same as Step 2 of the 3NF procedure.) 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 X → Y1, ..., X → Yn; 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.
Let Z be an element of S such that the projection P of R on the attributes of Z is not in BCNF; let X → Y be an FD of C that holds in P; and let X not be a superkey for P. Replace Z in S by (a) the union of X and Y and (b) the difference Z − Y between Z and Y (in that order). Perform this step for each distinct Z and each distinct X.
At the conclusion of this procedure, the elements of S are the headings of a set of BCNF relvars into which R can be nonloss decomposed, though not necessarily without losing FDs. Also, let me point out for the record that the procedure makes no mention of either 2NF or 3NF.