Implementation of Logical Query Languages for Databases

摘要

We examine methods of implementing queries about relational databases in the case that these queries are expressed in first-order logic as a collection of Horn clauses. Because queries may be defined recursively, straightforward methods of query evaluation do not always work, and a variety of strategies have been proposed to handle subsets of recursive queries. We shall express such query evaluation techniques as 'capture rules' on a graph representing clauses and predicates. The essential property of capture rules is that they can be applied independently, thus providing a clean interface for query-evaluation systems that use several different strategies in different situations. We show how rules suggested previously can be fit into this framework, and we propose some new capture rules and generalizations of old ones. (Author)