Implementation of logical query languages for databases

The area of database query evaluation is relatively well understood, as is shown by a recent survey article [1]. The two basic strategies are bottom-up, which creates intermediate relations (using, e.g., sort-merge joining), and top-down, which avoids intermediate relations by means of indexing and relation scanning. These two approaches each have relative advantages, and are intermixed in many standard implementations. The same principles apply to recursive queries, but their interaction is much less understood; in fact, lately there has been heated debate between adherents of PROLOG (top-down) and Deductive Databases (bottom-up). The present paper is the first serious attempt at merging these techniques.