Databases Reference
In-Depth Information
Definition:
Let
X
and
Y
be subsets of the heading of relvar
R
; then the
functional dependency
(FD)
X
→
Y
holds in
R
if and only if, whenever two tuples of
R
agree on
X
, they also agree on
Y
.
X
and
Y
are the
determinant
and the
dependant
, respectively, and the FD overall can be read as either “
X
functionally
determines
Y
” or “
Y
is functionally dependent on
X
,” or more simply just as “
X
arrow
Y
.”
For example, the FD {CITY} → {STATUS} holds in relvar S, as we know. Note the braces, by the way;
X
and
Y
in the definition are subsets of the heading of
R
, and are therefore
sets
(of attributes), even when, as in
the example, they happen to be
singleton
sets. By the same token,
X
and
Y
values are
tuples
, even when, as in the
example, they happen to be tuples of degree one.
By way of another example, the FD {SNO} → {SNAME,STATUS} also holds in relvar S, because {SNO}
is a key—in fact, the only key—for that relvar, and there are
always
“arrows out of keys” (see the section “Keys”
immediately following this one).
Note:
In case it isn't obvious, I use the term “arrow out of
X
” to mean there exists
some
Y
such that the FD
X
→
Y
holds in the pertinent relvar (where
X
and
Y
are subsets of the heading of that
relvar).
Now here's a useful thing to remember: If the FD
X
→
Y
holds in relvar
R
, then the FD
X
+
→
Y
-
also holds
in relvar
R
for all supersets
X
+
of
X
and all subsets
Y
-
of
Y
(just so long as
X
+
is still a subset of the heading, of
course). In other words, you can always add attributes to the determinant or subtract them from the dependant, and
what you get will still be an FD that holds in the relvar in question. For example, here's another FD that holds in
relvar S:
{ SNO , CITY }
→
{ STATUS }
(I started with the FD {SNO} → {SNAME,STATUS}, added CITY to the determinant, and dropped SNAME from
the dependant.)
I also need to explain what it means for an FD to be
trivial:
Definition:
The FD
X
→
Y
is
trivial
if and only if there's no way it can be violated.
For example, the following FDs all hold trivially for any relvar with attributes called STATUS and CITY:
5
{ CITY , STATUS }
→
{ CITY }
{ CITY , STATUS }
→
{ STATUS }
{ CITY }
→
{ CITY }
{ CITY }
→
{ }
To elaborate briefly (but considering just the first of these examples, for simplicity): If two tuples have the
same value for CITY and STATUS, they certainly have the same value for CITY. In fact, it's easy to see the FD
X
→
Y
is trivial if and only if
Y
is a subset of
X
. Now, when we're doing database design, we don't usually bother
with trivial FDs because they're, well, trivial; but when we're trying to be formal and precise about these matters—
5
In connection with the last of these examples in particular, see Exercise 4.10.
