Databases Reference
In-Depth Information
Note:
In logic, something that's identically true, such as the boolean expression CITY = CITY, is called a
tautology
. Thus, we can say the identity restriction of relvar
R
is any restriction in which the restriction condition is
a tautology.
I remark in passing that any given relvar
R
also always has an
empty
restriction, which we can denote thus:
R
WHERE FALSE
The (disjoint!) union of the identity restriction and the empty restriction of a given relvar
R
is of course identically
equal to
R
.
Note:
In logic, something that's identically false, such as the boolean expression CITY ≠ CITY, is
called a
contradiction
; thus, we can say the empty restriction of relvar
R
is any restriction in which the restriction
condition is a contradiction.
13
MORE ON THE CONFLICT
To revert to the main theme of the chapter: By now we've seen several examples in which FDs might be lost. In
most of those examples, we could avoid losing the FD by being careful; in one case, however (the SJT example), the
objectives of preserving FDs and BCNF decomposition were genuinely in conflict with each other. So the obvious
question arises: Can we characterize those cases where there really is a conflict? The answer is yes; in fact, it's
easy to do so.
Let
R
be the relvar we're dealing with, and let
C
be an irreducible cover for the FDs that hold in
R
. Construct
an
FD graph
as follows:
1.
Construct a node for each attribute of
R
.
2.
Let
X
→
Y
be an FD in
C
for which
X
involves two or more attributes; construct a “supernode” containing
just the nodes for the attributes named in
X
. (If you're doing this on paper, you could draw a circle enclosing
the individual attribute nodes.) Supernodes are considered to be nodes. Repeat this step for each FD in
C
for
which the determinant is composite.
3.
Let
X
→
Y
be an FD in
C
. Draw a directed arc from the node for
X
to the node for
Y
. Repeat this step for
each FD in
C
.
4.
If and only if the finished graph contains any cycles (where a cycle is a sequence of directed arcs from a node
to itself), then
R
cannot be nonloss decomposed into BCNF projections without losing an FD.
As an exercise, try applying the foregoing procedure to the various examples discussed earlier in the chapter.
When you do, you'll quickly understand (if you haven't done so already) what's really going on here. To spell the
point out: There's a genuine conflict only if the relvar involves a pattern of FDs akin to the pattern that obtains in
the SJT example.
13
The term
contradiction
doesn't mean quite the same in logic as it does in ordinary discourse, but the difference isn't important for present
purposes.
