SLDMagic - An Improved Magic Set Technique

A new version with a general bottom-up evaluator is now available. The rules of the meta-interpreter are defined as facts in the program, the partial evaluator would also work with other rules. This is a big improvement over the earlier version. The program actually became shorter by using the new general approach. The new version also recognizes facts which are known to be true at compiletime (i.e. derived unconditionally by the partial evaluator) and removes pure copy rules.

The copy rule elimination could be improved to make the resulting programs still smaller. I will continue to work on this, please visit this page again.

The last update was posted on March 20, 2000.

The Prolog code was written by Stefan Brass, Please contact sbrass@sis.pitt.edu if you wish to get informed about updates or if you found a bug.

The Program is available under the GNU Public License free of charge, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.

The following files are identical except a few lines commented out at the beginning.

• Prolog-Code with setting for SWI-Prolog and Quintus-Prolog
• Prolog-Code with setting for ECLiPSe-Prolog

After loading the program, call sldmagic(Filename).

• The syntax of input programs is pure Datalog (without function symbols).
• EDB-predicates must be declared in the form db(Pred/Arity). The declaration must precede any use of the EDB-predicates.
• If use_query_const(yes). is selected, the constants of the query will be compiled into the rewritten program. Otherwise, they will be replaced by parameters. The setting of options must precede any use of the option, so it is best done at the very beginning (options cannot be redefined).
• If derive_idb_literals(yes) is selected, the IDB-literals will be derived instead of answer-literals. If a variable is repeated or constants are known, answer-literals have fewer arguments, but propably a real IDB-literal looks better. Note that while normally the output program is guaranteed to be allowed (safe), if you use this option, and there are answers with variables in them, they will be derived.
  Finally, I decided not to store information on the arguments of conditional facts of answer-literals when derive_idb_literals(yes) is selected. So if e.g. answer(sg(X0,X0)) is derived, the program will assume that it might be possible to derive facts of the form answer(sg(X0,X1)). Of course, the transformation is correct, but it would discover only at runtime that all derived facts actually have the form answer(sg(X0,X0)). If you want to use the complete information at compiletime, choose derive_idb_literals(no).
• The query has the form :- Atom. At the moment, we assume for simplicity that only IDB-predicates are queried (queries to EDB-literals need no rewriting).

• Tail-Recursive Transitive Closure   [Output]
• Example showing Constant Propagation   [Output]
• Example without EDB-Predicates (All computation is done at compiletime.)   [Output]
• Same Generation   [Output]

Bra95b

S. Brass: Magic Sets vs. SLD-Resolution. In J. Eder, L. A. Kalinichenko (eds.), Advances in Databases and Information Systems (ADBIS'95), Springer, 1995, 185-203.

• Abstract or Paper (ps, 97K) or Paper (dvi, 31K)

Bra96a

S. Brass: SLDMagic - An Improved Magic Set Technique. In: B. Novikov, J. W. Schmidt (eds.): Advances in Databases and Information Systems - ADBIS'96, MEPhI Publishing, Moscow, 1996, 75-83. Also published in Springer Workshops in Computing (1997).

• Abstract
• Paper (ps, 59K) [Download from Hannover]
• Springer EWiC

• Database Systems & Logic Programming (Trier)
• Deductive Database Systems (Trier)
• Deductive Databases (Michael Gertz)