Journal of the ACM Bibliography

Seppo Sippu and Eljas Soisalon-Soininen. An analysis of magic sets and related optimization strategies for logic queries. Journal of the ACM, 43(6):1046-1088, November 1996. [BibTeX entry]
Abstract

We analyze the optimization effect of the ``magic sets'' rewriting technique for datalog queries and present some supplementary or alternative techniques that avoid many shortcomings of the basic technique. Given a magic sets rewritten query, the set of facts generated for the original, nonmagic predicates by the seminaive bottom-up evaluation is characterized precisely. It is shown that -- because of the additional magic facts -- magic sets processing may result in generating an order of magnitude more facts than the straightforward naive evaluation. A refinement of magic sets called factorized magic sets is defined. These magic sets retain most of the efficiency of original magic sets in regards to the number of nonmagic facts generated and have the property that a linear-time bound with respect to seminaive evaluation is guaranteed in all cases. An alternative technique for magic sets, called envelopes, which has several desirable properties over magic sets, is introduced. Envelope predicates are never recursive with the original predicates; thus, envelopes can be computes as a preprocessing task. Envelopes also allow the utilization of multiple sideways information passing strategies (sips) for a rule. An envelope-transformed program may be ``readorned'' according to another choice of sips and reoptimized by magic sets (or envelopes), thus making possible an optimization effect that cannot be achieved by magic sets based on a particular choice of sips.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in:

Categories and Subject Descriptors: H.2.4 [Database Management]: Systems -- query processing; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving -- logic programming

General Terms: Algorithms, Languages, Theory

Additional Key Words and Phrases: Datalog, envelopes, logic query, magic sets

Selected references


Shortcuts:

  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database