Two-phase abstract interpretation, the analysis technique for logic programs proposed by Byeong-Mo Chang, provides an approximation of success patterns of clauses relevant to a given query. The analysis result from two-phase abstract interpretation can be utilized to improve the bottom-up query evaluation of logic program by reducing the generation of irrelevant facts during evaluation and to improve the top-down execution models by determining some subgoals which will definitely fail or some succeeding subgoals which will not participate in any success pattern of program clauses relevant to a given query.
We implemented a filtered bottom-up evaluator using abstract filter computed by two-phase abstract interpretation and a top-down evaluator based linear execution model, which is improved by applying the analysis result from two-phase abstract interpretation. Experiments show the efficiency of the evaluations using two-phase abstract interpretation in comparison with other related evaluation methods.
