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
.
