Abstract interpretation: A kind of magic

AbstractMagic sets and, more recently, magic templates have been used in the field of deductive databases to facilitate efficient bottom-up evaluation of database queries. Roughly speaking a top-down computation of a definite logic program is simulated by first transforming the program and then executing the new program bottom-up. In this paper we give a new and very simple proof that this approach is equivalent to the collecting interpretation of the abstract interpretation framework for logic programs of Mellish. As a side-effect we are also able to show that “bottom-up” abstract interpretation based on the magic templates transformation is equally powerful as Mellish's abstract interpretation framework, but less powerful than other (more precise) abstract interpretation frameworks