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