What’s formal is normal
What’s not so is not
And if normal is formal,
Informal is what?
Now I want to step back, take a deep breath as it were, and consider FDs and BCNF all over again—but this time I want to do it properly (with apologies for the small amount of repetition involved). As you’ll quickly see, the treatment in this chapter is rather more abstract than that in the previous one; it shouldn’t be difficult to follow, if you’re fully comfortable with the material of that previous chapter, but it’ll certainly be more formal. For that reason, I don’t want you to look at this chapter at all until you’ve absorbed everything in the previous one. (Of course, that shouldn’t be hard to do, since most of what was in that chapter was surely familiar to you anyway.)
One general point up front: Since BCNF is the normal form with respect to FDs, I won’t have anything to say in this chapter regarding 2NF or 3NF (or indeed 1NF). As I’ve more or less said already, 2NF and 3NF just aren’t all that interesting in themselves.
In this section I simply give definitions, with little by way of further elaboration, of a few familiar but absolutely fundamental concepts—definitions that are rather more precise than the ones typically found in the literature (as well as being more precise, in some cases, than ones given earlier in this book). Production of examples to illustrate the definitions is left as an exercise.
Definition: A heading H is a set of attribute names. Note: I remind you that this definition is deliberately not quite the same as the one I gave in Chapter 2, q.v. Also, for reasons that aren’t important here, The Third Manifesto uses {H}, not H, to denote a heading; however, the simpler form H is more convenient for the purposes of this book.
Definition: A tuple with heading H is a set of ordered pairs <A,v> (one such pair for each attribute name A appearing in H), where v is a value. Note: The phrase tuple with heading H can be abbreviated to just tuple, if H is either understood or irrelevant for the purpose at hand.
Definition: Let t be a tuple with heading H and let X be a subset of H. Then the (tuple) projection t{X} of t on the attributes of X is a tuple with heading X—namely, that subset of t containing just those <A,v> pairs such that A appears in X.[45] Note: Here I’m defining a version of the usual relational projection operator that applies to individual tuples (see Exercise 2.11). Observe that every projection of a tuple is itself a tuple.
Definition: A relation r is an ordered pair <H,h>, where h is a set of tuples (the body of r) all having heading H. H is the heading of r and the attributes of H are the attributes of r. The tuples of h are the tuples of r.
Definition: Let r be the relation <H,h> and let X be a subset of H. Then the (relational) projection r{X} of r on the attributes of X is the relation <X,x>, where x is the set of all tuples t{X} such that t is a tuple of h.
Definition: Let relations r1, ..., rn (n ≥ 0) be joinable—i.e., let them be such that attributes with the same name are of the same type. Then the join of r1, ..., rn, JOIN {r1,...,rn}, is a relation with (a) heading the union of the headings of r1, ..., rn and (b) body the set of all tuples t such that t is the union of a tuple from r1, ..., and a tuple from rn. Note: This version of join is what’s sometimes called, more explicitly, the natural join. Note that it’s an n-adic operator, not a dyadic operator merely (n = 2 is just a common special case; as for n < 2, see Exercise 3.1). Note also that join degenerates to cartesian product in the important special case in which the operand relations r1, ..., rn have no attributes with the same name.
Definition: A relation variable or relvar with heading H is a variable R such that a value r can be assigned to that variable only if that value r is a relation with heading H. The attributes of H are the attributes of R. Also, if relation r is assigned to R, then the body and tuples of r are the body and tuples of R, respectively, under that assignment. Note: As the definition says, relation r can be assigned to relvar R only if (emphasis added) it has the same heading as R. In fact, relation r can be assigned to relvar R if and only if (a) it has the same heading as R and(b) it satisfies all of the constraints that apply to R—where “all of the constraints that apply to R” includes FDs that hold in R but (in general) isn’t limited to such FDs alone.
[45] There’s a tiny notational complication here. If X is a subset of H, then X is a set of attribute names, {A1,...,An} say, and the projection t{X}of t on X would thus apparently have to be written with double braces, like this: t{{A1,...,An}}. Of course we don’t do this, and I’m going to ignore this complication throughout the remainder of the book. However, I should at least explain why it arises. Basically, it does so because we’re conflating two distinct interpretations of the symbol X. On the one hand, we’re using that symbol to mean the set as such—i.e., the set whose elements are A1, ..., An; on the other hand, we’re using it to mean the commalist of attribute names A1, ... An as physically written that represents those elements (on paper, say). The former is what the symbol X actually denotes; the latter is the way we express that denotation in concrete syntax.