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)
giaco@lix.polytechnique.fr
Abstract:
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