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 }