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
.
