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
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.
(I have tested Version 2 only with SWI-Prolog.
Version 1 did run on all these three Prologs.
I will do further tests soon.)
After loading the program,
Sorry for this brewity.
An improved manual will be available soon.
Maybe also an
The syntax of input programs is pure Datalog
(without function symbols).
EDB-predicates must be declared in the form
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.
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)
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
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,
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).
Magic Sets vs. SLD-Resolution.
In J. Eder, L. A. Kalinichenko (eds.),
Advances in Databases and Information Systems (ADBIS'95),
Springer, 1995, 185-203.
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).
Please tell my about further related links by email.
firstname.lastname@example.org), March 20, 2000.