Databases Reference
In-Depth Information
In this latter JD, however, the {SNAME,CITY} component is irrelevant: It's a proper subset of another component,
and for that reason the corresponding projection isn't needed in the process of reconstructing the original relvar.
With the foregoing example by way of motivation, I can now give a precise definition of what it means for
some component to be irrelevant in some JD:
Definition:
Let
{
X1
,...,
Xn
} be a JD,
J
say; then
Xi
is
irrelevant
in
J
if and only if (a) there exists some
Xj
in
J
such that
Xi
is a proper subset of
Xj
or (b
)
there exists some
Xj
in
J
(
i
<
j
) such that
Xi
=
Xj
.
1
The reason for my choice of the term
irrelevant
here is as follows: If
Xi
is irrelevant in
J
, then every relation
that satisfies
J
also satisfies
J′
, where
J′
is derived from
J
by dropping
Xi
. What's more, the converse is true too:
Every relation that satisfies
J′
also satisfies
J
. In other words, the JDs
J
and
J′
are
equivalent:
Every relation that
satisfies either one necessarily satisfies the other one as well. As a consequence, irrelevant components can't just
always be dropped, they can always be added too, without significant effect.
COMBINING COMPONENTS
So now we've seen that some JDs imply other JDs (just as some FDs imply other FDs). But irrelevant components
are far from being the end of the story. The next point is as follows (I've labeled it a theorem, but it's very obvious
and scarcely merits such a grand designation):
Theorem:
Let
J
be a JD and let
J′
be derived from
J
by replacing two components by their union. Then
J
implies
J′
(that is, every relation that satisfies
J
also satisfies
J′
).
By way of example, every legal value of relvar S satisfies the following JD (it's the JD from the previous
section, with an irrelevant component)─
{ { SNO , SNAME , CITY } , { CITY , STATUS } , { SNAME , CITY } }
─and therefore satisfies this one too:
{ { SNO , SNAME , CITY } , { CITY , STATUS , SNAME } }
Exercise:
Check the validity of the foregoing claim for yourself─maybe even try to prove it, formally─if it isn't
immediately obvious. (Also, how many distinct JDs can be derived from the given one by combining components
in this manner?) Points arising:
I made use of the foregoing theorem, tacitly, when I explained the intuition behind the membership algorithm
(for testing whether a JD is implied by keys) in Chapter 10.
Observe that the theorem involves an implication, not an equivalence:
J
implies
J′
, but the converse isn't
true─
J′
doesn't imply
J
, in general, and so
J
and
J′
aren't equivalent (again, in general).
Note:
In fact this
point is easy to see: If we keep on replacing components by their union, we'll eventually obtain one that's
1
If we assume the components
X1
, ...,
Xn
are all distinct, we can drop part (b) of this definition.
