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:
