Databases Reference

In-Depth Information

But the components of J2 form a proper subset of those of J1. It follows that J1 is reducible with respect to

S. To be specific, the component {CITY,STATUS} can be dropped from J1 without loss, in the sense that

what remains is still a JD of S.

Observe now that the foregoing proof made no use of the fact that the FD {CITY} → {STATUS} holds in S

(indeed, the result would still be valid even if that FD didn't hold). But now let's do another example that does

make use of that FD:

First, we know now that the following JD (J1 from the previous example) holds in S:

{ { SNO , CITY } , { CITY , STATUS } , { SNO , STATUS } }

But the FD {CITY} → {STATUS} also holds, and so by Heath's Theorem the following JD─let's call it

J3─holds as well:

{ { CITY , STATUS } , { CITY , SNO } }

The components of J3 form a proper subset of those of J1, and so it follows once again that J1 is reducible

with respect to S. To be specific, the component {SNO,STATUS} can be dropped from J1 without loss, in

the sense that what remains is still a JD of S.

Observe, therefore, that the original JD J1 is equivalent, with respect to relvar S, to two distinct JDs: namely,

J2 and J3.

In general, of course, the question is: Given relvar
R
and a JD
J
that holds in
R
, how can we find an

irreducible equivalent (meaning, to be more precise about the matter, a JD that's both equivalent to
J
and

irreducible, where
equivalent
and
irreducible
are both understood as being with respect to
R
)? Well:

If some component is irrelevant in
J
, that component can clearly be dropped.

If all components are relevant, we can only try dropping one, and then:

a.

If what's left is still a JD of
R
, we drop another component and repeat the process.

b.

If what's left isn't a JD of
R
, we reinstate the dropped component and try dropping another one.

Eventually, we'll arrive at a JD that's equivalent to the original one and is irreducible.

And how do we tell whether some JD is in fact a JD of
R
? Well, if it's one that's been explicitly declared as

such, there's clearly no problem; but if not, we use the
chase
, which I'll be describing in the next section but one.

SUMMARY SO FAR

Let me summarize where we are. The general point is that some JDs imply others. As specific illustrations of this

point, we've discussed: