Abstract Filters: Improving Bottom-up Executions of Logic Programs by Two-phase Abstract Interpretation

By: B.M. Chang, K.M. Choe and R. Giacobazzi

Roberto Giacobazzi
LIX, Laboratoire d'Informatique
Ecole Polytechnique
91128 Palaiseau cedex(Paris)


Bottom-up evaluation of logic programs may be inefficient as it may generate many irrelevant facts to a given query. The filtering strategy prevents possible irrelevant facts from being processed in the bottom-up evaluation on system graphs. This paper defines the filtered bottom-up evaluation formally, and provides a new filter called abstract filter which is computed by two-phase abstract interpretation at compile time. The abstract filter is defined on a generic abstract domain. This framework is specialized on the depth k abstract domain of Sato and Tamaki. The abstract filter is shown to be at least as powerful as the static filter on the depth k abstract domain. Some performance results are provided.

Available: DVI, PostScript, BibTeX Entry.

Roberto Giacobazzi@di.unipi.it