Database Design and Relational Theory

Chapter 7. FD Axiomatization

[The] true and solid and living axioms

—Francis Bacon: The New Organon

I’ve touched on the point several times already that some FDs imply others; now it’s time to get more specific. First of all, however, I need to introduce some notation—notation that (a) reduces the number of keystrokes required in formal proofs and the like and (b) can also help, sometimes, to see the forest as well as the trees, as it were.

As you might recall, the statement of Heath’s Theorem in Chapter 5 included the following sentence: Let XY denote the union of X and Y, and similarly for XZ. The notation I want to introduce is basically just an extension of this simple idea (it’s a trifle illogical, but it’s very convenient). To be specific, the notation uses expressions of the form XY to mean:

• The union of {X} and {Y}, if X and Y denote individual attributes (i.e., are individual attribute names)

• The union of X and Y, if X and Y denote sets of attributes (i.e., are sets of attribute names)

It also allows {X} to be abbreviated to just X (e.g., in an FD) if X denotes an individual attribute. Note: For convenience, I’ll refer to this notation from this point forward as Heath notation.

ARMSTRONG’S AXIOMS

We’ve seen that, formally speaking, an FD is just an expression of the form X → Y, where X and Y are sets (actually sets of attribute names, but from a formal point of view it really doesn’t matter what the sets consist of). Now, suppose we’re given some set (F, say) of FDs. Then we can ...