Databases Reference

In-Depth Information

CHAPTER 10

10.1 a. No (see the discussion of relvar SPJ in the body of the chapter for a counterexample). b. No (in fact,

as was shown in the answer to Exercise 4.6, a binary relvar isn't necessarily even in BCNF, or even in 2NF).

c. No (see Chapter 13). d. No (again, see Chapter 13). e. See the body of the chapter. f. No (see relvar CTXD in

Chapter 9 for a counterexample; see also Chapter 15).

10.2

See the body of the chapter.

10.3 First, I assume no JD has any repeated components, for otherwise the number of JDs would literally be

infinite. Second, relvar SP is in 5NF, and in fact in 6NF; we haven't discussed 6NF yet (see Chapter 13), but I can

at least say that if a relvar is in 6NF, then all of the JDs that hold in that relvar will be trivial ones. So the question

becomes: How many trivial JDs hold in relvar SP? Well, all such JDs take the form
{
H
,
X1
,...,
Xn
}, where
H

denotes the entire heading and {
X1
,...,
Xn
} is a set─possibly empty─of proper subsets of
H
. Since
H
is of degree

three, it has eight subsets, of which all but one are proper. How many distinct sets are there whose elements are

some subset of a prescribed set of seven elements? Well, there's one such set with no elements at all; there are

seven such sets with just one element; and, more generally, there are “7 pick
i
” such sets with
i
elements (
i
= 0, 1, ...,

7).
8
So the total number of sets of proper subsets of
H
= (7 pick 0) + (7 pick 1) + (7 pick 2) + ... + (7 pick 7) = 1 + 7

+ 21 + 35 + 35 + 21 + 7 + 1 = 128. So there are 128 trivial JDs that hold in relvar SP.
Note:
Of those 128, 64

involve an empty component, which might reasonably be ignored─for example, the JDs
{
H
,{}} and
{
H
} are

clearly equivalent
9
─thereby reducing the total count to 64.

10.4

See the body of the chapter.

10.5 For the definition, see the body of the chapter. Since an FD isn't a JD but merely implies one, a trivial FD

isn't a special case. However, the JD implied by a trivial FD is indeed itself trivial in turn. For example, the trivial

FD {CITY,STATUS} → {STATUS} holds in the suppliers relvar S. Applying Heath's Theorem, therefore, we see

the trivial JD
{
AB
,
AC
} holds in S, where
A
is {CITY,STATUS},
B
is {STATUS}, and
C
is {SNO,SNAME} (and

hence
AC
is the entire heading).

10.6 For an example of a tuple forcing JD, see the SPJ example in the body of the chapter. As for one that's not

tuple forcing, consider, e.g., the JD
{{SNO,SNAME,CITY},{CITY,STATUS}} that holds in relvar S (which fails

to be tuple forcing, observe, precisely because it has a component that's a superkey for the pertinent relvar).

10.7 Examples can be obtained from the examples given in the body of the chapter in connection with relvar SPJ

by systematically replacing supplier numbers by RNO values, part numbers by ANO values, and project numbers by

PNO values.
No further answer provided.

10.8 Well, obviously I don't know whether you have any comments, but I certainly do. However, I don't think it

would be polite to air them here, so I won't.

8
In general, the expression “
n
pick
r
” denotes the number of ways of picking
r
elements from a set of
n
elements.

9
Proof
: For all relations
r
, JOIN{
r
{
H
},
r
{}} = JOIN{
r
} =
r
.