An optimization strategy for recursive queries in logic databases

We consider the optimization of recursive database queries expressed in Datalog (function-free Horn clause programs). We present a general strategy for rewriting a Datalog program to cut down the number of database facts consulted in the bottom-up evaluation of queries containing bound arguments. The strategy can be interpreted as a preprocessing task in which an `envelope' containing the facts relevant to the query is determined by computing an easily evaluable query, and then the original query is applied to facts belonging to this envelope, which usually is only a small subset of all facts. The strategy applies to any Datalog program, and there exists a variant of the basic strategy that always produces `regular envelopes' that can be determined using a regularly recursive program.