Databases Reference
In-Depth Information
Note carefully that FDs are defined with respect to some
heading
, not with respect to some relation or some
relvar. The two FDs just shown, for example, are defined with respect to any heading that contains attributes CITY,
STATUS, and SNO (and others as well, possibly).
Note too that from a formal point of view, an FD is just an
expression:
an expression that, when interpreted
with respect to some specific relation, becomes a
proposition
that, by definition, evaluates to either TRUE or
FALSE. For example, if the two FDs shown above are interpreted with respect to the relation that's the current
value of relvar S (Fig. 1.1), then the first evaluates to TRUE and the second to FALSE. Of course, it's common
informally to define such an expression to be an FD, in some specific context, only if it evaluates to TRUE in that
context; but such a definition leaves no way of saying a given relation fails to satisfy, or violates, some FD. Why
so? Because, by that informal definition, an FD that isn't satisfied wouldn't be an FD in the first place! For
example, we wouldn't be able to say the relation that's the current value of relvar S violates the second of the FDs
shown above.
I really can't stress the foregoing point strongly enough. For most people, it represents a shift in thinking;
but it's a shift that has to be made if you're ever to understand what design theory is all about. The point is this:
Most writings on FDs—including the early research papers that first introduced the concept—don't actually define
the concept of an FD, as such, at all! Instead, they say something along the lines of “
Y
is functionally dependent on
X
if and only if, whenever two tuples agree on
X
, they also agree on
Y
.” Which is perfectly true, of course—but it's
not a definition of an FD; instead, it's a definition of what it means for an FD to be
satisfied
. But if we want to
develop a theory of FDs as such, then we clearly need to be able to talk about FDs as objects in their own right,
divorced from the context of some particular relation or relvar. More specifically, we need to divorce the concept of
an FD as such from the concept that it might have some interpretation, or meaning, in some context. In fact, design
theory can be regarded as a small piece of logic, and logic isn't about meaning at all—it's about formal
manipulations.
To continue with the definitions:
Definition:
Let relation
r
have heading
H
and let
X
→
Y
be an FD,
F
say, with respect to
H
. If all pairs of
tuples
t1
and
t2
of
r
are such that whenever
t1
{
X
} =
t2
{
X
}, then
t1
{
Y
} =
t2
{
Y
}, then
r
satisfies
F
; otherwise
r
violates
F
.
Observe that it's relations, not relvars, that satisfy or violate some given FD. For example, the relation that's
the current value of relvar S satisfies both of these FDs—
{ CITY }
→
{ STATUS }
{ SNAME }
→
{ CITY }
—and violates this one:
{ CITY }
→
{ SNO }
Definition:
The FD
F
holds
in relvar
R
(equivalently, relvar
R
is subject to
the FD
F
) if and only if every
relation that can be assigned to relvar
R
satisfies
F
. The FDs that hold in relvar
R
are
the FDs of
R
.
Important:
Please note the terminological distinction I'm drawing here—FDs are
satisfied
(or violated) by
relations, but
hold
(or don't hold)
in relvars. Please note too that I'll adhere to this distinction throughout this topic.
By way of example, the following FD holds in relvar S—
{ CITY }
→
{ STATUS }
