So much for 1NF; now I can begin to discuss some of the higher normal forms. Now, I’ve already said that Boyce/Codd normal form (BCNF) is defined in terms of functional dependencies, and in fact the same is true of second normal form (2NF) and third normal form (3NF) as well. Here then is a definition:
Definition: Let X and Y be subsets of the heading of relvar R; then the functional dependency (FD)
X → Y
holds in R if and only if, whenever two tuples of R agree on X, they also agree on Y. X and Y are the determinant and the dependant, respectively, and the FD overall can be read as either “X functionally determines Y” or “Y is functionally dependent on X,” or more simply just as “X arrow Y.”
For example, the FD {CITY} → {STATUS} holds in relvar S, as we know. Note the braces, by the way; X and Y in the definition are subsets of the heading of R, and are therefore sets (of attributes), even when, as in the example, they happen to be singleton sets. By the same token, X and Y values are tuples, even when, as in the example, they happen to be tuples of degree one.
By way of another example, the FD {SNO} → {SNAME,STATUS} also holds in relvar S, because {SNO} is a key—in fact, the only key—for that relvar, and there are always “arrows out of keys” (see the section KEYS immediately following this one). Note: In case it isn’t obvious, I use the term “arrow out of X” to mean there exists some Y such that the FD X → Y holds in the pertinent relvar (where X and Y are subsets of the heading of that relvar).
Now here’s a useful thing to remember: If the FD X → Y holds in relvar R, then the FD X+ → Y- also holds in relvar R for all supersets X+ of X and all subsets Y- of Y (just so long as X+ is still a subset of the heading, of course). In other words, you can always add attributes to the determinant or subtract them from the dependant, and what you get will still be an FD that holds in the relvar in question. For example, here’s another FD that holds in relvar S:
{ SNO , CITY } → { STATUS }(I started with the FD {SNO} → {SNAME,STATUS}, added CITY to the determinant, and dropped SNAME from the dependant.)
I also need to explain what it means for an FD to be trivial:
Definition: The FD X → Y is trivial if and only if there’s no way it can be violated.
For example, the following FDs all hold trivially for any relvar with attributes called STATUS and CITY:[38]
{ CITY , STATUS } → { CITY }
{ CITY , STATUS } → { STATUS }
{ CITY } → { CITY }
{ CITY } → { }To elaborate briefly (but considering just the first of these examples, for simplicity): If two tuples have the same value for CITY and STATUS, they certainly have the same value for CITY. In fact, it’s easy to see the FD X → Y is trivial if and only if Y is a subset of X. Now, when we’re doing database design, we don’t usually bother with trivial FDs because they’re, well, trivial; but when we’re trying to be formal and precise about these matters—in particular, when we’re trying to develop a theory of design—then we need to take all FDs into account, trivial ones as well as nontrivial.