Databases Reference

In-Depth Information

This procedure overall will eventually yield either:

a.

A representation of the conclusion of
d
, in which case
d
does follow from
D
, or

b.

A relation that satisfies
D
but not
d
, in which case
d
doesn't follow from
D
.

Let's do an example. Let the given set of dependencies be as follows (Heath notation once again):

{
A
→
C
,
B
→
C
,
C
→
D
,
CE
→
A
,
DE
→
C
}

(Actually they're all FDs, as you can see.) Consider also the following JD (call it
J
):

{
AB
,
AD
,
AE
,
BE
,
CDE
}

I'll now show that the given FDs do in fact imply
J
(a state of affairs that, I'll think you agree, isn't immediately

obvious).

The first step is to write down tuples representing the premises of the JD
J
. Now, let me spell out exactly

what that JD says:

If all of the following are the case─

a tuple appears with
A
=
a
and
B
=
b

a tuple appears with
A
=
a
and
D
=
d

a tuple appears with
A
=
a
and
E
=
e

a tuple appears with
B
=
b
and
E
=
e

a tuple appears with
C
=
c
and
D
=
d
and
E
=
e

─then

a tuple with
A
=
a
and
B
=
b
and
C
=
c
and
D
=
d
and
E
=
e
must appear.

However, it turns out to be more convenient to use, not
a
,
b
,
c
,
d
, and
e
as such, but rather suffixed
x
's and

y
's to denote attribute values. To be specific, I'll use
x1-x5
in place of
a-e
, respectively, and I'll use
y
's in all other

positions; e.g., I'll use
y23
to denote the “third” or
C
value in the “second” premise tuple. So the premise tuples

look like this:
7

x1 x2 y13 y14 y15

x1 y22 y23 x4 y25

x1 y32 y33 y34 x5

y41 x2 y43 y44 x5

y51 y52 x3 x4 x5

If (and only if) the JD is implied by the five FDs, then, these tuples will “generate” the following tuple:

x1 x2 x3 x4 x5

7
Strictly speaking, the premise tuples aren't really tuples at all, because they contain variables instead of values. Likewise, the premise tuples

taken together don't really constitute a relation, either. I propose to overlook these points from here on; however, I should at least mention in

passing that─partly for such reasons─the research literature typically refers to those premise tuples as constituting not a relation but a
tableau
.