Databases Reference
In-Depth Information
Given some set
D
of dependencies (FDs or JDs or a mixture), what dependencies
d
are implied by those in
that set?
A partial answer to this question is provided by
the chase algorithm
, which is, precisely, an algorithm for
testing whether some dependency
d
is implied by a set of dependencies
D
. More specifically, given the set
D
and
some dependency
d
, the chase will either:
a.
Show
d
is implied by
D
, or
b.
Show it isn't, by providing an explicit counterexample─that is, a relation that satisfies all of the dependencies
in
D
and yet violates
d
.
As a matter of fact we've already seen some examples of the chase in action, as it were. In the previous
section, I showed how a given FD and JD together implied a certain FD and not another (the latter was actually a
key constraint, which is a special case of an FD, of course). And in the section before that, I gave two examples in
which a given FD and JD together implied a certain JD (thereby showing the given JD was reducible, incidentally).
All of these examples were in fact applications of the chase. But now let's get more specific. In order to do that, I
first need to introduce a little more terminology:
Consider FDs. Abstractly (though of course very loosely), an FD takes the form “If certain tuples
t1
, ...,
tn
appear, then certain attributes within those tuples must have equal values.” For this reason, FDs are
sometimes said to be
equality generating
dependencies.
Now consider JDs. Abstractly, but again very loosely, a JD takes the form “If certain tuples
t1
, ...,
tn
appear,
then a certain tuple
t
must appear.” JDs are therefore sometimes said to be
tuple generating
dependencies.
Before going any further, I must caution you not to confuse tuple generating and tuple
forcing
dependencies.
6
A tuple
forcing
dependency is a JD with the property that if tuples
t1
, ...,
tn
appear, then some tuple
t
is forced to
appear that's distinct from each of
t1
, ...,
tn
. By contrast, a tuple
generating
dependency (a) doesn't require the
“generated” tuple to be distinct from the given tuples and (b) doesn't in fact have to be a JD, as such, at all.
(However, the only tuple generating dependencies discussed in this topic are indeed JDs specifically. For present
purposes, therefore, you can take “tuple generating dependency” to mean a JD; thus, we can say that all tuple
forcing dependencies are tuple generating, but some tuple generating dependencies aren't tuple forcing.)
Equality generating and tuple generating dependencies both involve a set of
premises
─viz., the tuples
t1
, ...,
tn
─and a
conclusion
. For a tuple generating dependency, the conclusion is the generated tuple
t
; for an equality
generating dependency, it's the fact that a certain equality holds.
Now I can explain the chase algorithm as such. Perhaps I should say first that it's essentially common sense;
in fact, it tends to be easier to illustrate than to describe. In outline, however, it works like this. We're trying to
determine whether the dependency
d
follows from the dependencies in the set
D
. We proceed as follows:
1.
We write down tuples representing the premises of
d
.
2.
We apply the dependencies in
D
to those tuples (possibly generating additional tuples), and keep repeating
this process until no further change occurs.
6
By the same token, don't confuse
equality
generating
dependencies and
equality
dependencies, mentioned in an earlier footnote in this chapter
and elsewhere and discussed in detail in Chapter 13.
