With a proper understanding of FDs under our belt, as it were, I can now go on to tackle the question of what it means for a relvar to be in BCNF. Again I proceed by means of a series of precise definitions.
Now, in Chapter 4 I defined a trivial FD to be one that can’t possibly be violated. There’s nothing wrong with that definition, of course; however, the one just given is preferable because it explicitly mentions the pertinent heading. I also said in Chapter 4 that it’s easy to see the FD X → Y is trivial if and only if Y is a subset of X. Well, that’s true too; but I can now say that this latter fact isn’t really a definition but rather a theorem, easily proved from the definition as such. (On the other hand, the definition as such isn’t very helpful in determining whether a given FD is trivial, whereas the theorem is. For that reason, we might regard the theorem as an operational definition, inasmuch as it does provide an effective test that can easily be applied.)[46] Let me state the theorem explicitly for the record:
Theorem: Let X → Y be an FD, F say. Then F is trivial if and only if the dependant Y is a subset of the determinant X.
Now back to the definitions:
Definition: A superkey of relvar R is a subset SK of the heading H of R such that the FD SK → H holds in R (“is an FD of R”). That FD is a superkey constraint on R.
For example, {SNO}, {SNO,CITY}, and {SNO,CITY,STATUS} are all superkeys for relvar S.
Definition: The FD X → Y is irreducible with respect to relvar R (or just irreducible, if R is understood) if and only if it holds in R and X- → Y doesn’t hold in R for any proper subset X- of X.
For example, the FD {CITY} → {STATUS} is irreducible with respect to relvar S. By contrast, the FD {CITY,SNO} → {STATUS}, though certainly an FD of S, is reducible with respect to S. Observe that while FDs as such are defined with respect to some heading, FD irreducibility is defined with respect to some relvar. In other words, FDs as such are just a syntactic notion (an FD is just an expression that takes a certain syntactic form), while FD irreducibility is a matter of semantics (it has to do with what the pertinent relvar means). Note: I won’t assume in what follows that the FDs we’re talking about are irreducible ones only, though in practice we typically do.
Definition: A key of relvar R is a subset K of the heading H of R such that the FD K → H is an irreducible FD of R. That FD is a key constraint on R.
Note the appeal to FD irreducibility in the foregoing definition.
Definition: Let relvar R have heading H and let X → Y be an FD, F say, with respect to H. Then F is implied by the keys of R if and only if every relation r that satisfies R’s key constraints also satisfies F.
This definition requires some elaboration. First of all, to say some relation satisfies some key constraint is to say it satisfies the applicable uniqueness requirement; and if it satisfies the uniqueness requirement for the set of attributes that constitute some key, it certainly also satisfies the uniqueness requirement for every superset of that set of attributes (just so long as that superset is a subset of the pertinent heading, of course)—in other words, for every corresponding superkey. Thus, the phrase “satisfies R’s key constraints” in the definition could be replaced by the phrase “satisfies R’s superkey constraints” without making any significant difference. Likewise, the concept “implied by keys” could just as well be “implied by superkeys,” again without making any significant difference.
Second, what happens if the FD F mentioned in the definition is trivial? Well, in that case, by definition, F is satisfied by every relation r with heading H, and so F is certainly satisfied by every relation r that satisfies R’s key constraints, a fortiori. So trivial FDs are always “implied by keys,” trivially.
Third, then, suppose F is nontrivial. Then it’s easy to prove the following theorem:
Theorem: Let F be an FD that holds in relvar R. Then F is implied by the keys of R if and only if it’s a superkey constraint on R.
In other words, it’s like that business with trivial FDs: The formal definition as such isn’t very helpful in determining whether a given FD is implied by keys, but the theorem is. For that reason, we can regard the theorem as an operational definition, since it does provide an effective test that can easily be applied in practice.
And now, at last, I can define BCNF:
Definition: Relvar R is in Boyce-Codd normal form (BCNF) if and only if every FD of R is implied by the keys of R.
However, given the various definitions and theorems already discussed in this section, we can see that the following “operational” definition is valid too:
Definition: Relvar R is in Boyce-Codd normal form (BCNF) if and only for every nontrivial FD X → Y that holds in R, X is a superkey for R.
As I put it in Chapter 4, it follows from this definition that the only FDs that hold in a BCNF relvar are either trivial ones (we can’t get rid of those, obviously) or arrows out of superkeys (we can’t get rid of those, either). Though now I’d like to add that when I talk about “getting rid of” some FD, I fear I’m being—I hope uncharacteristically—a little sloppy ... For example, consider relvar S. That relvar is subject to the FD {CITY} → {STATUS}, among others; as explained in Chapter 3, therefore, the recommendation is to decompose the relvar into its projections SNC on {SNO,SNAME,CITY} and CT on {CITY,STATUS}. But if we do, then the FD {SNO} → {STATUS}, which also holds in relvar S, “disappears,” in a sense; thus we have indeed “gotten rid of it.” But what does it mean to say the FD has disappeared? The answer is: It’s been replaced by a multirelvar constraint (that is, a constraint that spans two or more relvars). So the constraint certainly still exists—it just isn’t an FD any more.[47] Similar remarks apply whenever I talk, elsewhere in this book, of “getting rid of” some dependency.
[46] Distinctions like the one I’m drawing here are sometimes characterized as semantic vs. syntactic distinctions. To spell the point out: The original definition—F is trivial if and only if it’s satisfied by every relation with the pertinent heading—is semantic, because it defines what the concept means; by contrast, what I’ve called the “operational” definition—F is trivial if and only if Y is a subset of X—is syntactic, because it provides a check that can be performed in a purely syntactic way. (We’ll be meeting this distinction, between semantic and syntactic notions, many times in the pages ahead. In fact, one case in point arises almost immediately in connection with the notion of FD irreducibility, q.v.)
[47] Well ... it is an FD, but one that holds in the join of two relvars, viz., SNC and CT, rather than in an individual relvar as such. Note, however, that enforcing the key constraints on those two relvars will enforce that multirelvar constraint “automatically”; that is, the multirelvar constraint in question is implied by, or is a logical consequence of, certain explicitly declared constraints.