On the other hand, there are a number of optimization strategies that allow query answering by bottom-up evaluation. Generalized Magic Sets rewriting is such an optimization technique that has been developed for query answering in deductive databases [\protect\citeauthoryearBeeri and Ramakrishnan1991]. We have adapted this rewriting technique to achieve bottom-up abduction of Horn knowledge bases [\protect\citeauthoryearBurgun and Hinkelmann].
The scheme of our abduction rewriting approach is presented in Fig. 6. Given a theory and a goal we first perform a Generalized Magic Sets rewriting. In a second step we further transform this rulebase with respect to the set of abducibles. Evaluating the resulting abduction rulebase by bottom-up evaluation will compute all abductive solutions.
The transformation can be regarded as a specialization of a partially evaluated upside-down meta-interpreter originally presented by Stickel [\protect\citeauthoryearStickel1991] (see also [\protect\citeauthoryearInoue et al.1993]). Compared to Stickel's approach we have a number of advantages:
Most important: this set-oriented approach is usable also for large sets of facts. This is supports our objective to develop techniques suitable not only for toy examples but also for complex real world problems with databases and large knowledge bases.