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.
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.
Search WWH ::

Custom Search