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).
