Databases Reference

In-Depth Information

of its own. However, by the time this point was sufficiently recognized, Fagin had already defined what he called

fourth normal form, so
that
name wasn't available.
10
Hence the anomalous name
Boyce/Codd normal form
.

EXERCISES

4.1

How many FDs hold in relvar SP? Which ones are trivial? Which are irreducible?

4.2

Is it true that the concept of FD relies on the notion of tuple equality?

4.3 Give examples from your own work environment of (a) a relvar not in 2NF; (b) a relvar in 3NF but not 2NF;

(c) a relvar in BCNF but not 3NF.

4.4

Prove the two definitions of 2NF given in the body of the chapter are logically equivalent.

4.5

Is it true that if a relvar isn't in 2NF, then it must have a composite key?

4.6

Is it true that every binary relvar is in BCNF?

4.7

(
Same as Exercise 1.4.
) Is it true that every “all key” relvar is in BCNF?

4.8 Write
Tutorial D
CONSTRAINT statements to express the FDs {SNO} → {SNAME} and {SNAME} →

{SNO} that hold in relvar SNP (see the section “Boyce/Codd Normal Form”).
Note:
This is the first exercise in any

chapter that asks you to give an answer in
Tutorial D
. Of course, I realize you might not be completely conversant

with that language; in all such exercises, therefore—for example, Exercises 4.14 and 4.15 below—please just do the

best you can. I do think it worth your while at least to attempt the exercises in question.

4.9 Let
R
be a relvar of degree
n
. What's the maximum number of FDs that can possibly hold in
R
(trivial as

well as nontrivial)? What's the maximum number of keys it can have?

4.10

Given that
X
and
Y
in the FD
X
→
Y
are both sets of attributes, what happens if either is the empty set?

4.11

Can you think of a situation in which it really would be reasonable to have a base relvar with an RVA?

4.12 There's a lot of discussion in the industry at the time of writing of
XML databases
. But XML documents are

inherently hierarchic in nature; so do you think the criticisms of hierarchies in the body of the chapter apply to XML

databases? (Well, yes, they do, as I indicated in a footnote earlier in the chapter. So what do you conclude?)

4.13 In Chapter 1, I said I'd be indicating primary key attributes, in tabular pictures of relations, by double

underlining. At that point, however, I hadn't properly discussed the difference between relations and relvars; and

now we know that keys in general apply to relvars, not relations. Yet we've seen several tabular pictures since then

that represent relations as such (I mean, relations that aren't just a sample value for some relvar)—see, e.g., Fig. 4.1

10
Actually, when Raymond Boyce first came up with what became that “new and improved” normal form, he did call it fourth normal form!

(The paper in which he first described the concept─
IBM Technical Disclosure Bulletin 16
, No. 1 (June 1973)─had the title “Fourth Normal Form

and its Associated Decomposition Algorithm.”) I don't know why that name was subsequently rejected (though I have my suspicions).