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:
