SLDMagic—An Improved Magic Set Technique

We present a rewriting method for Datalog-programs which simulates SLD-resolution more closely than the ordinary “magic set” method does. This is especially advantageous in the case of tail-recursive programs, but already in nonrecursive programs we can often save a number of joins. In contrast to the method of ROSS [7], we do not only solve the problem of tail-recursion, but try to simulate SLD-resolution as fully as possible. An especially nice feature of our approach is that we get many other known optimizations “for free” in this way. Based on an idea of BRY [3], our method can be described in an elegantway by means of a meta-interpreter. This also allows to compare the efficiency of SLD-resolution and magic sets within a common framework. We then develop a combined method, which allows to choose the evaluation strategy for every body literal.