Databases Reference

In-Depth Information

CHAPTER 11

11.1
Which JDs are trivial?
None.
Which ones involve irrelevant components?
i., k., and l.
Which imply others?

a. implies b.; d. implies g. and h.; e. implies g.; f. implies h. and i.; j. implies k.
Which pairs are equivalent?
None.

Which are satisfied by the sample value in Fig. 1.1?
a., b., c., d., e., g., and l.
Which hold in relvar P?
a., b., c., e.,

and l.
Which are irreducible?
a., b., c., and e.

11.2

a.

By Heath's Theorem, the answer is obviously yes (take
X
as
A
,
Y
as
BC
, and
Z
as
D
). But let's see if we can

prove this result using the chase. Premise tuples:

x1 y12 y13 x4

x1 x2 x3 y24

From the FD
A
→
B
, we have
y12
=
x2
; from the FD
A
→
C
, we have
y13
=
x3
. Make the replacements:

x1 x2 x3 x4

x1 x2 x3 y24

Now we have a tuple of all
x
's, and the desired result follows. The given JD does follow from the given JDs.

b.

Premise tuples:

x1 x2 y13 y14

y21 x2 x3 y24

y31 y32 x3 x4

The FDs imply
y24
=
x4
and
y13
=
x3
. Make the replacements:

x1 x2 x3 y14

y21 x2 x3 x4

y31 y32 x3 x4

The FD
C
→
D
now implies
y14
=
x4
; making the replacement gives us a tuple of all
x
's, and so the result

follows: The given JD does follow from the given FDs. Note that we had to use one of the FDs twice in the

chase in this example. Note too that we could have obtained the same result by applying Heath's Theorem

twice: The FD
C
→
D
implies the JD
{
CD
,
CAB
}, which in turn implies the JD
{
CD
,
BC
,
BA
}, thanks to

the FD
B
→
C
.

c.

I leave it to you to show the answer here is
no
.

d.

Premise tuples:

x1 x2 y13 y14

y21 x2 x3 y24

y31 y32 x3 x4

Applying the JD
{
BC
,
ABD
} to the tuples with a common
B
value (viz.,
x2
) generates the following tuples: