## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# THE CHASE ALGORITHM

From everything we’ve seen in this chapter so far, the obvious question presents itself:

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:

1. Show d is implied by D, or

2. 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required