Magic conditions
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan · 1990
Much recent work has focussed on the bottom-up evaluation of Datalog programs. One approach, called Magic-Sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts ([BMSU86, BR87, Ram88]). It is widely believed that the principal application of the Magic-Sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the Magic-Set transformation to use predicates other than equality (X > 10, for example). This Extended Magic-Set technique has practical utility in “real” relational databases, not only for recursive queries, but for non-recursive queries as well; in ([MFPR90]) we use the results in this paper and those in [MPR89] to define a magic-set transformation for relational databases supporting SQL and its extensions, going on to describe an implementation of magic in Starburst ([HFLP89]). We also give preliminary performance measurements.