Databases Reference

In-Depth Information

Another direction for design research therefore consists of examining the implications of decomposing

relvars by some operator other than projection. In the example, the decomposition operator is, as already mentioned,

(disjoint) restriction; the corresponding recomposition operator is (disjoint) union. Thus, it might be possible to

construct a “restriction-union” normalization theory, analogous to—but orthogonal to—the projection-join

normalization theory we've been considering prior to this point. I don't want to get much more specific on such

matters here; suffice it to say that some initial ideas along these lines can be found (a) in Fagin's PJ/NF paper, which

additionally discusses a normal form called PJSU/NF, and (b) in a paper by Smith, which discusses a normal form

called (3,3)NF.
20
This latter paper, incidentally, shows that (3,3)NF implies BCNF, but that a (3,3)NF relvar need

not be in 4NF, nor need a 4NF relvar be in (3,3)NF. As suggested above, therefore, reduction to (3,3)NF is

orthogonal to reduction to 4NF (and 5NF).

EXERCISES

13.1

Draw the normal form hierarchy from memory. Include at least nine normal forms.

13.2

Define 6NF.

13.3 6NF relvars are sometimes said to be irreducible, and I noted in the body of the chapter that this was yet

another of the many kinds of irreducibility that are relevant to design theory. How many different kinds can you

identify?

13.4

Define (a) FD redundancy; (b) JD redundancy; (c) RFNF.

13.5 Take another look at the decomposition of relvar P in the body of the chapter into 6NF projections PN, PL,

PW, and PC. Can you think of any improvements on that design?

13.6 You're given a relvar
R
representing marriages, with attributes
A
,
B
, and
C
and predicate
Person A married

person B on date C
. Assume no polygamy; assume also that no two persons marry each other more than once.

What keys does
R
have? Does the JD
{
AB
,
BC
,
CA
} hold? What's the highest normal form
R
is in?

13.7 In the body of the chapter, I said a relvar could be in SKNF and not 5NF, and I proposed the following as an

example of such a relvar:

Let relvar
R
have attributes
A
,
B
, and
C
(only); let
AB
,
BC
, and
CA
each be keys of
R
; and let the JD

{
AB
,
BC
,
CA
}─call it
J
─hold in
R
.

But you might not unreasonably be a little suspicious of this example. To be more specific, you might be wondering

whether a relvar could even exist that's subject to exactly the specified key constraints and the specified JD (even

though I did go on to give a slightly more concrete version of the example). Show the example is reasonable after

all by demonstrating that in fact all possible sets of dependencies (FDs and JDs) are consistent, in the sense that at

least one relation can always be found that satisfies all dependencies in the set.

20
J. M. Smith, “A Normal Form for Abstract Syntax,” Proc. 4th Int. Conf. on Very Large Data Bases, Berlin, Federal German Republic

(September 1978).