Databases Reference
In-Depth Information
respectively, and then joining r1 and r2 back together again. I now show that, conversely, every tuple of the join is
indeed a tuple of r (in other words, the join doesn't generate any “spurious” tuples). Let ( a , b , c ) ∈ JOIN { r1 , r2 }. In
order to generate such a tuple in the join, we must have ( a , b ) ∈ r1 and ( a , c ) ∈ r2 . Hence there must exist tuples
( a , b , c′ ) ∈ r and ( a , b′ , c ) ∈ r for some b′ and some c′ . But r satisfies { A } → { B }; hence b = b′ , and so ( a , b , c ) ∈ r .
The next simplest case is the one in which X , Y , and Z aren't necessarily singleton sets but are pairwise
disjoint. In this case, we can regard the attributes constituting X as a single composite attribute (and similarly for Y
and Z ), and the argument of the previous paragraph then applies directly.
We now need to consider what happens if X , Y , and Z aren't pairwise disjoint. There are three cases to
consider: X and Y not disjoint, X and Z not disjoint, and Y and Z not disjoint.
First, then, let X and Y not be disjoint, but let X and Z be disjoint and let Y and Z be disjoint (hence Z =
H - XY ). Recall now that if X Y is satisfied, then so is X + Y - for all subsets Y - of Y . It follows that the FD X
Y - X is satisfied. But X and Y - X are disjoint; by the previous result, therefore, r is equal to the join of its
projections on (a) the union of X and Y - X and (b) XZ . But (again) X and Y - X are disjoint, so their union is equal
to XY . So the theorem applies in this case also, and we can (and I will) assume without loss of generality in the
remainder of the proof that X and Y are disjoint.
Now let X and Z not be disjoint, but let Y and Z be disjoint. By the previous result, then, r is equal to the join
of its projections on (a) XY and (b) the union of X and Z - X . But the union of X and Z - X is equal to XZ . So the
theorem applies in this case also, and we can (and I will) assume without loss of generality in the remainder of the
proof that X and Z are disjoint.
Now let Y and Z not be disjoint. Let W = Z - Y . Since r satisfies the FD X Y , then, it also satisfies the FD
X Y - W , and Y - W and Z are disjoint. By the previous result, therefore, r is equal to the join of its projections
on (a) the union of X and Y - W and (b) XZ . I now appeal to a lemma, easily proved (see below), to the effect that if
(a) r1 and r2 are projections of r such that JOIN{ r1 , r2 } = r , (b) H′ is a subset of H but a superset of the heading of
r1 , and (c) r′ is the projection of r on H′ , then (d) JOIN{ r′ , r2 } = r ; in other words, loosely, r1 can be extended with
arbitrary attributes of r2 without altering the result of the join. From this lemma, it follows immediately that r is
equal to the join of its projections on XY and XZ ; so the theorem applies in this case also. Conclusion: Heath's
Theorem is valid in all possible cases.
Lemma: Let r have heading H and let H be partitioned into A , B , C , and D , and assume for simplicity that
none of these four subsets is empty. (Extending the proof to cover the case where that assumption fails to
hold is left as a subsidiary exercise.) Without loss of generality, we can treat A , B , C , and D as if they were
individual attributes. So let r1 = R { A , B } and r2 = r { B , C , D }, and let ( a , b ) ∈ r1 and ( b , c , d ) ∈ r2 . Since r =
JOIN{ r1 , r2 }, it follows that ( a , b , c , d ) ∈ r ; hence ( a , b , c ) ∈ r { A , B , C } and ( b , c , d ) ∈ r { B , C , D }; hence ( a , b , c , d )
∈ JOIN{ r { A , B , C }, r { B , C , D }}. The desired result follows─ r { B , C , D } is r2 , and r { A , B , C } can be taken as r′ ,
with H′ = { A , B , C }. End of lemma.
The converse of Heath's Theorem would say that if relation r is equal to the join of its projections on XY and
XZ , then r satisfies the FD X Y . This converse is false. To show this is so, it's sufficient to exhibit a
counterexample. So consider a relvar CTX, with attributes CNO (course), TNO (teacher), and XNO (textbook), and
predicate Course CNO can be taught by teacher TNO and uses textbook XNO . Here's a sample value for this relvar:

Search WWH ::

Custom Search