Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    SLDMagic - An Improved Magic Set Technique

    Advances in Databases and Information Systems '96

    Moscow. 10th - 13th September 1996


    S. Brass


    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 elegant way 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.


    PDF filePDF Version of this Paper (175kb)