Databases Reference

In-Depth Information

So let's see if it does; i.e., let's apply the given dependencies.

From
A
→
C
, we have
y13
=
y23
=
y33
; likewise, from
B
→
C
, we have
y13
=
y43
. So we can replace each

of
y23
,
y33
, and
y43
by
y13
. The premise tuples become (replacements shown in
bold
):

x1 x2 y13 y14 y15

x1 y22
y13
x4 y25

x1 y32
y13
y34 x5

y41 x2
y13
y44 x5

y51 y52 x3 x4 x5

From
C
→
D
, we have
y14
=
y34
=
y44
=
x4
. Make the replacements:

x1 x2 y13
x4
y15

x1 y22 y13 x4 y25

x1 y32 y13
x4
x5

y41 x2 y13
x4
x5

y51 y52 x3 x4 x5

From
CE
→
A
, we have
y41
=
x1
. Make the replacements:

x1 x2 y13 x4 y15

x1 y22 y13 x4 y25

x1 y32 y13 x4 x5

x1
x2 y13 x4 x5

y51 y52 x3 x4 x5

From
DE
→
C
, we have
y13
=
x3
. Make the replacements:

x1 x2
x3
x4 y15

x1 y22
x3
x4 y25

x1 y32
x3
x4 x5

x1 x2
x3
x4 x5
◄═
Success:
all x's !!!

y51 y52 x3 x4 x5

The “fourth” tuple here is all
x
's, and so the JD
J
does indeed follow from the given FDs.

Let's look at another example. Let the given set of dependencies consist of just the JD {
AB
,
AC
}. Does this

set imply the FD
A
→
B
?
Note:
We already know the answer is no, because what we're talking about here is the

converse of Heath's Theorem, and we know from Exercise 5.4 that the converse of Heath's Theorem is false. But

let's see what the chase tells us:

Premise tuples:

x1 y12 y13

x1 y22 y23

If and only if the FD is implied by the JD, then applying the JD to these tuples will have to make
y12
and
y22

equal. Does it do so? Well:

The given JD “generates” tuples as follows: