Databases Reference
In-Depth Information
equal to the entire heading, and the resulting JD
J′
will be trivial─and it's clearly not the case that every JD is
equivalent to some trivial JD.
Although it's true that the second of the two JDs shown above (the binary one) holds in relvar S, nonloss
decomposing that relvar on the basis of that JD would
not
be a good idea.
Note:
Exercise 11.4 asks you to
explain this observation further, but you might like to take a moment now to convince yourself that it's true.
Also─to get ahead of myself for a moment─I can say the JD in question is in fact
irreducible
with respect to
S (see the section immediately following). What the example shows, therefore, is that although irreducible
JDs are important, they don't necessarily correspond to good decompositions. Informally, in other words, we
need to distinguish between “good” and “bad” JDs, where “good” and “bad” refer to the quality of the
corresponding decompositions. For further discussion, see Chapter 14.
IRREDUCIBLE JDs
So far the notion of one JD implying another has been more or less syntactic in nature─I haven't really paid much
attention to the question of whether the JDs we're talking about actually hold in some given relvar. (Observe that
neither the definition of irrelevant components, nor the theorem about replacing components by their union, made
any mention of a relvar, nor even of a heading.) Now, however, let's consider JDs that do actually hold in some
relvar. Then we have the following theorem:
Theorem:
Let JD
J
hold in relvar
R
; then
J
is
equivalent
to some irreducible JD (not necessarily unique)
that also holds in
R
. Note, however, that
equivalence
here has to be understood in the context of some
particular relvar; it's possible for two JDs both to hold in one relvar and not both to hold in another. In such
a case, the two JDs might or might not be equivalent with respect to the first relvar, but they're certainly not
equivalent with respect to the second.
I'll explain exactly what it means for a JD to be irreducible in a moment. Before I do, however, let me just
remind you of a parallel with the world of FDs. Recall from Part II of this topic that every FD that holds in relvar
R
implies some irreducible FD that also holds in relvar
R
. (This is easy to see: Just keep dropping attributes from the
determinant until what remains is an FD that no longer holds.) Similarly, every JD that holds in relvar
R
implies─in
fact, is equivalent to (a stronger statement)─some irreducible JD that also holds in relvar
R
.
So what does it mean for a JD to be irreducible? Here's a definition:
Definition:
Let
{
X1
,...,
Xn
} be a JD,
J
say, that holds in relvar
R
, and let there be no proper subset
{
Y1
,...,
Ym
} of {
X1
,...,
Xn
} such that the JD
{
Y1
,...,
Ym
} also holds in
R
. Then
J
is
irreducible with respect
to
R
(or just
irreducible
, if
R
is understood).
Points arising:
It's easy to see that every JD that holds in relvar
R
implies an irreducible JD that also holds in relvar
R
─just
keep dropping components from the given JD until what's left is a JD that no longer holds in
R
, and then the
last one that does hold is irreducible.
It's also easy to see that the implication goes the other way, too: Start with the irreducible JD and add the
dropped components back in until the original JD is reached. At each step in this process, the current version
of the JD will be a JD that holds in
R
.
Note:
From this point and the previous point taken together, it follows
