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.
