Databases Reference

In-Depth Information

x1 y12 y23

x1 y22 y13

The four tuples taken together satisfy the JD but not the FD; in particular, they don't require that
y12
=
y22
.

So the FD doesn't follow from the JD.

CONCLUDING REMARKS

In this chapter, we've seen JDs implying JDs; a JD and an FD together implying an FD; FDs implying a JD; and, in

earlier chapters, FDs implying FDs. However, note carefully that all the chase lets us do is determine whether a

specific
dependency follows from given dependencies. What it doesn't do is let us
infer
, or
generate
, new

dependencies from the given set (that's why I said, near the beginning of the previous section, that the chase

provided only a partial answer to the question). For that, we'd need an axiomatization for FDs and JDs. And while

Armstrong's rules provide a sound and complete axiomatization for FDs by themselves, it's unfortunately a known

fact that no such axiomatization exists for FDs and JDs considered together.
8

EXERCISES

11.1 Consider the parts relvar P from the suppliers-and-parts database. For simplicity, let's rename attributes

PNO, PNAME, COLOR, WEIGHT, and CITY as
A
,
B
,
C
,
D
, and
E
, respectively, and let's use Heath notation once

again. Then the following JDs are all defined with respect to the heading of P:

a.
{
AC
,
ABDE
}

b.
{
ACD
,
ABDE
}

c.
{
AE
,
ABCD
}

d.
{
AB
,
ACD
,
CE
}

e.
{
AB
,
ACD
,
AE
}

f.
{
AB
,
BCD
,
DE
}

g.
{
ABC
,
ACDE
,
CE
}

h.
{
ABCD
,
BDE
,
BCE
}

i.
{
AB
,
ABC
,
BCD
,
CDE
,
AD
}

j.
{
AB
,
BC
,
CD
,
DE
,
AD
}

k.
{
ABD
,
CDE
,
ABC
,
BE
,
ABE
}

l.

{
A
,
AB
,
ABC
,
ABD
,
ACE
}

Which of these JDs are trivial? Which ones involve irrelevant components? Which imply which others in the

list? Which pairs are equivalent to one another? Which are satisfied by the sample value of relvar P shown in

Fig. 1.1? Which hold in relvar P? Which are irreducible with respect to P?

11.2

The dependencies in this exercise are all defined with respect to a heading consisting of attributes
ABCD
.

a.

Does the set of FDs {
A
→
B
,
A
→
C
} imply the JD
{
AD
,
ABC
}?

8
See, e.g., the topic
Foundations of Databases
, by Serge Abiteboul, Richard Hull, and Victor Vianu (Addison-Wesley, 1995).