Improving goal directed bottom-up evaluation of logic programs
(English)Manuscript (preprint) (Other academic)
This paper introduces a new strategy for goal directed bottom-up evaluation of logic programs. The strategy is based on a combination of two known techniques: dividing a program into strongly connected components (SCC) and Induced Magic-sets.
In our approach no magic transformation is needed (as in Induced Magic-sets). We introduce a notion of a call-success dependency graph that constructed directly from the original program. Its SCCs are used to optimize a fixpoint computation (i.e. they coincide with SCCs of a corresponding magic program). The new graph contains substantially fewer edges than standard dependency graph of a magic program, and thus its SCCs are computed faster. We also show how to incorporate SCC-based optimization into the Unduced Magic-sets technique. This is achived by modifying the basic Induced Magic method, so that the fixpoints are computed locally for every SCC.
The impact of our method is illustrated by experimental results.
magic-sets, bottom-up evaluation
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-87997OAI: oai:DiVA.org:liu-87997DiVA: diva2:601007