Databases Reference
In-Depth Information
“implicitly” because we haven't been told the FD holds explicitly. The question is: Can we prove (a) and (b), given
only that the stated FD and JD hold? That is, can we show that (a) and (b) are valid formally , without paying any
regard to semantics? (After all, that's what the system would have to do, if we wanted it to be able to infer
dependencies. The system doesn't know anything about semantics, as I'm using that term here.) 5
So let's give it a try. First of all, suppose the following tuples appear in SPT:
s1 p1 t2
s1 p2 t1
Suppose also that p1 p2 . Now what we need to do, in order to show the FD {SNO} → {STATUS} holds, is to
show that t1 and t2 must necessarily be equal. We begin by writing down the projections of these two tuples
corresponding to the components of the given JD {{SNO,PNO},{SNO,STATUS}}:
s1 p1 s1 t2
s1 p2 s1 t1
Joining these projections together, we obtain the original two tuples plus two extra ones (shown below in bold ):
s1 p1 t2
s1 p1 t1
s1 p2 t2
s1 p2 t1
Since the given JD holds, the two extra tuples must in fact appear in the relvar along with the original two.
But the FD {SNO,PNO} → {STATUS} holds also; it follows that t1 = t2 , and hence that the FD {SNO} →
{STATUS} holds (every tuple that has SNO s1 also has STATUS t1 ). This is part (b) of what was to be proved. At
the same time, by our assumption we have p1 p2 ─note that nothing in the argument so far invalidates that
assumption─from which it follows that the FD {SNO} → {PNO} doesn't hold, and so {SNO} isn't a key; and this
is part (a) of what was to be proved.
So we see that any given relvar is subject to both explicit dependencies (these are the ones explicitly
declared) and implicit dependencies (these are the ones implied by the explicitly declared ones). For the record, let
me bring these points together into an appropriate definition:
Definition: Let R be a relvar. Associated with R are two sets of explicit dependencies: a set XFD of explicit
FDs that hold in R and a set XJD of explicit JDs that hold in R . The FDs in XFD together with the JDs in
XJD are the explicit dependencies of R . The FDs and JDs that aren't in XFD or XJD but are logical
consequences of the ones in XFD and XJD are the implicit dependencies of R . The explicit and implicit
dependencies of R taken together are the dependencies of R . A relation r can be assigned to R only if that
relation r satisfies all of the dependencies of R .
THE CHASE ALGORITHM
From everything we've seen in this chapter so far, the obvious question presents itself:
5 I note in passing that a proof of part (b) follows immediately from what Exercise 11.3, q.v., refers to as the converse of an extended version of
Heath's theorem.
Search WWH ::

Custom Search