Databases Reference
In-Depth Information
4.7 Yes. If no nontrivial FDs hold at all─which is certainly the case for an “all key” relvar─then there's no
nontrivial FD that holds for which the determinant
isn't
a superkey, and so the relvar is in BCNF.
4.8
CONSTRAINT ...
COUNT ( SNP { SNO , SNAME } ) = COUNT ( SNP { SNO } ) ;
CONSTRAINT ...
COUNT ( SNP { SNO , SNAME } ) = COUNT ( SNP { SNAME } ) ;
By the way, this trick for specifying that an FD holds─i.e., by stating that two projections have the same
cardinality─certainly does the job; as noted in Chapter 2, however, it's hardly very elegant, and for that reason I
showed a different approach, using AND, RENAME, and JOIN, in that chapter. Alternatively, Hugh Darwen and I
have proposed
3
that
Tutorial D
should support another form of CONSTRAINT statement in which the usual
boolean expression is replaced by the combination of a relational expression and one or more key specifications.
Using this syntax, the foregoing constraints could be stated thus:
CONSTRAINT ... SNP { SNO , SNAME } KEY { SNO } KEY { SNAME };
Explanation:
Think of the relational expression─SNP{SNO,SNAME}, in the example─as defining some temporary
relvar (perhaps a view); then the key specifications─KEY {SNO} and KEY{SNAME}, in the example
above─indicates that the specified attributes constitute keys for that relvar.
As an aside, I note that Darwen and I have also proposed allowing foreign key constraints to be specified for
expressions in the same kind of way.
4.9 Let the FD
X
→
Y
hold in
R
. By definition,
X
and
Y
are subsets of the heading of
R
. Given that a set of
n
elements has 2
ⁿ
possible subsets, it follows that each of
X
and
Y
has 2
ⁿ
possible values, and hence an upper limit on
the number of possible FDs that might hold in
R
is 2
²ⁿ
. For example, if
R
is of degree five, the maximum number of
FDs that might hold is 1,024 (of which 243 are trivial).
Subsidiary exercises:
(a) Where did that figure of 243 come
from? (b) Suppose those 1,024 FDs do all in fact hold. What can we conclude about
R
in that case? (
Answer:
It
must have cardinality less than two. The reason is that one FD that holds in such a case is {} →
H
, where
H
is the
heading; it follows that {} is a key, and so
R
is constrained to contain at most one tuple, as explained in the answer
to the next exercise.)
As for how many keys
R
can have: Let
m
be the smallest integer greater than or equal to
n
/2.
R
will have the
maximum possible number of keys if either (a) every distinct set of
m
attributes is a key or (b)
m
is odd and every
distinct set of (
m
-
1) attributes is a key. Either way, it follows that the maximum number of keys is
n
! / (
m
! *
(
n
-
m
)!).
4
For example, a relvar of degree five can have at most ten distinct keys.
4.10 Let the specified FD
X
→
Y
hold in relvar
R
. Now,
every
tuple (regardless of whether it's a tuple of
R
) has
the same value─namely, the 0-tuple─for the projection of that tuple over the empty set of attributes. If
Y
is empty,
therefore, the FD
X
→
Y
holds for all possible sets
X
of attributes of
R
; in fact, it's a trivial FD (and so it isn't very
interesting), because the empty set is a subset of every set and so
Y
is definitely a subset of
X
in this case. On the
other hand, if
X
is empty, the FD
X
→
Y
means that, at any given time, all tuples of
R
have the same value for
Y
(since they certainly all have the same value for
X
). What's more, if
Y
in turn is the heading of
R
─in other words, if
X
is a superkey─then
R
is constrained to contain at most one tuple.
Note:
In this latter case,
X
isn't just a superkey
3
In our topic
Database Explorations: Essays on The Third Manifesto and Related Topics
(Trafford, 2010) and elsewhere.
4
The symbol
r
! is read as “
r
factorial” and denotes the product
r
* (
r
-
1) * … * 2 * 1.
