Databases Reference
InDepth Information
—and these ones don't:
{ SNAME }
→
{ CITY }
{ CITY }
→
{ SNO }
(Contrast the examples following the previous definition.) So now, at last, we know precisely what it means for a
given relvar to be subject to a given FD.
BOYCE/CODD NORMAL FORM
With a proper understanding of FDs under our belt, as it were, I can now go on to tackle the question of what it
means for a relvar to be in BCNF. Again I proceed by means of a series of precise definitions.
Definition:
Let
X
→
Y
be an FD,
F
say, with respect to heading
H
. Then
F
is
trivial
if and only if it's
satisfied by every relation with heading
H
.
Now, in Chapter 4 I defined a trivial FD to be one that can't possibly be violated. There's nothing wrong
with that definition, of course; however, the one just given is preferable because it explicitly mentions the pertinent
heading. I also said in Chapter 4 that it's easy to see the FD
X
→
Y
is trivial if and only if
Y
is a subset of
X
. Well,
that's true too; but I can now say that this latter fact isn't really a definition but rather a
theorem
, easily proved from
the definition as such. (On the other hand, the definition as such isn't very helpful in determining whether a given
FD is trivial, whereas the theorem is. For that reason, we might regard the theorem as an
operational
definition,
inasmuch as it does provide an effective test that can easily be applied.)
2
Let me state the theorem explicitly for the
record:
Theorem:
Let
X
→
Y
be an FD,
F
say. Then
F
is
trivial
if and only if the dependant
Y
is a subset of the
determinant
X
.
Now back to the definitions:
Definition:
A
superkey
of relvar
R
is a subset
SK
of the heading
H
of
R
such that the FD
SK
→
H
holds in
R
(“is an FD of
R
”). That FD is a
superkey constraint
on
R
.
For example, {SNO}, {SNO,CITY}, and {SNO,CITY,STATUS} are all superkeys for relvar S.
Definition:
The FD
X
→
Y
is
irreducible with respect to relvar
R
(or just
irreducible
, if
R
is understood) if
and only if it holds in
R
and
X

→
Y
doesn't hold in
R
for any proper subset
X

of
X
.
For example, the FD {CITY} → {STATUS} is irreducible with respect to relvar S. By contrast, the FD
{CITY,SNO} → {STATUS}, though certainly an FD of S, is
reducible
with respect to S. Observe that while FDs
as such are defined with respect to some
heading
, FD irreducibility is defined with respect to some
relvar
. In other
2
Distinctions like the one I'm drawing here are sometimes characterized as
semantic vs. syntactic
distinctions. To spell the point out: The
original definition—
F
is trivial if and only if it's satisfied by every relation with the pertinent heading—is semantic, because it defines what the
concept means; by contrast, what I've called the “operational” definition—
F
is trivial if and only if
Y
is a subset of
X
—is syntactic, because it
provides a check that can be performed in a purely syntactic way. (We'll be meeting this distinction, between semantic and syntactic notions,
many times in the pages ahead. In fact, one case in point arises almost immediately in connection with the notion of FD irreducibility, q.v.)