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:
Show d is implied by D , or
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:
We write down tuples representing the premises of d .
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.
Search WWH ::

Custom Search