Databases Reference
In-Depth Information
Note that it follows from the definition that the union of the components
X1
, ...,
Xn
must be equal to
H
(i.e.,
every attribute of
H
must appear in at least one of those components), for otherwise
R
couldn't possibly be
equal to the join of the projections that correspond to those components.
Different writers use different symbols to denote a JD; I use a special kind of star, but the symbol
⋈ﾠ(“bowﾠ
tie”)ﾠ
is more frequently encountered in the research literature.
It might help to point out that to say some JD holds is equivalent to saying that if we join the indicated
projections together, we'll never get any “spurious” tuples (as Exercise 3.2 called them).
The following observation might also be helpful. I'll explain it in terms of a simple, though slightly abstract,
example. Let relvar
R
have attributes
A
,
B
,
C
, and
D
(only), and let the JD
{
AB
,
BC
,
CD
} (“Heath
notation”—see Chapter 7) hold in
R
. Also, let me use the symbol “∈” to mean “appears in” (as in the answer
to Exercise 5.4 in Appendix D). Then to say the given JD holds in
R
is equivalent to saying the following:
4
if
EXISTS
c1
( EXISTS
d1
( (
a
,
b
,
c1
,
d1
)
∈
R
) ) AND
EXISTS
a2
( EXISTS
d2
( (
a2
,
b
,
c
,
d2
)
∈
R
) ) AND
EXISTS
a3
( EXISTS
b3
( (
a3
,
b3
,
c
,
d
)
∈
R
) )
then
(
a
,
b
,
c
,
d
)
∈
R
Explanation:
Let there be a tuple in
R
with
A
=
a
and
B
=
b
and
a tuple in
R
with
B
=
b
and
C
=
c
and
a
tuple in
R
with
C
=
c
and
D = d
. Then the tuples (
a
,
b
), (
b
,
c
), and (
c
,
d
) will appear in the projections of
R
on
AB
,
BC
, and
CD
, respectively, and so the tuple (
a
,
b
,
c
,
d
) will appear when we join these three projections
together. Moreover, the converse is clearly true as well: If the tuple (
a
,
b
,
c
,
d
) appears in
R
, then the tuples
(
a
,
b
), (
b
,
c
), and (
c
,
d
) will certainly appear in those three projections (and so that
If
in the foregoing formal
statement could in fact be replaced by
If and only if
).
As a simple illustration of this last point, to say the following JD holds in relvar S—
{ { SNO , SNAME , CITY } , { CITY , STATUS } }
—is to say the tuple (
s
,
n
,
t
,
c
) appears in S if and only if there's a tuple in S with SNO =
s
and SNAME =
n
and CITY
=
c
and
there's a tuple in S with CITY =
c
and STATUS =
t
.
To continue with this example for a moment, the fact that the specified JD holds in relvar S is a logical
consequence of Heath's Theorem, as we know. In fact, we can now restate Heath's Theorem as follows:
Heath's Theorem
(
for relvars, restated in terms of JDs
): Let relvar
R
have heading
H
and let
X
,
Y
, and
Z
be
subsets of
H
such that the union of
X
,
Y
, and
Z
is equal to
H
. Let
XY
denote the union of
X
and
Y
, and
similarly for
XZ
. If
R
is subject to the FD
X
→
Y
, then
R
is subject to the JD
{
XY
,
XZ
}.
As stated earlier, therefore, FDs imply JDs─but not all JDs are implied by FDs, as we'll see. Before I
elaborate on this point, however, let me stress the requirement that the union of the components of a given JD must
be equal to the pertinent heading. No analogous requirement applies to FDs; with FDs, the left and right sides don't
have to be such that their union is equal to the pertinent heading, they only have to be subsets of that heading. This
4
The keyword EXISTS in the following definition denotes the
existential quantifier
. Refer to
SQL and Relational Theory
if you need a tutorial
on such matters.
