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.
COUNT ( SNP { SNO , SNAME } ) = COUNT ( SNP { SNO } ) ;
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:
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.
Search WWH ::

Custom Search