Analysis of Magic Sets and Related Optimization Strategies for Logic Queries

摘要

The authors analyze the optimization effect of the 'magic sets' rewritingtechnique for datalog queries and present some supplementary or alternative techniques that avoid most shortcomings of the basic technique. The concept of a 'potentially relevant fact' is introduced to characterize the set of facts generated for the original (non-magic) predicates by the (semi)naive bottom-up evaluation of a magic sets rewritten query. A refinement of magic sets called 'factorized magic sets' is defined that, while retaining most of the efficiency of original magic sets as regards the non-magic facts generated, has the property that a true optimization effect over seminaive evaluation is guaranteed in all cases. An alternative technique for magic sets called 'envelopes' is introduced that has several desirable properties over magic sets. Envelope predicates are never recursive with the original predicates; thus envelopes can be computed as a preprocessing task. Envelopes also allow the utilization of multiple sideways information passing strategies (sips) for a rule.