Magic conditions

ABSTRACT

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. In extending Magic-Sets, we describe a natural generalization of the common class of bound (b) and free (ƒ) adornments. We also present a formalism to compare adornment classes.

REFERENCES

• BKMR89: Isaac Balbin, David B. Kemp, Krishnamurthy Meenakshi, and Kotagiri Ramamohanarao. Propagating Constraints in Recursive Deductive Databases. In North American Conference on Logic Programming (NACLP), Cleveland, Ohio, October 16-20 1989.
• BMSU86: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• BR87: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• HFLP89: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• HP88: Waqar Hasan and Hamid Pirahesh. Query Rewrite Optimization in Starburst. Research Report, RJ 6337 (62349), IBM Research Division, Computer Science, Almaden Research Center, San Jose, California 95120- 6099, August 4 1988.
• ISO88: ISO_ANSI. Working Draft; Database Language SQL2. 1988.
• MPR89: Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. Duplicates and Aggregates in Datalog. Research Report, IBM Reseaxch Division, Computer Science, Almaden Research Center, San Jose, California 95120-6099, December 1989.
• MFPR90: I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, ACM SIGMOD Record, v.19 n.2, p.247-258, Jun. 1990
• Mor88: Katherine A. Morris, An algorithm for ordering subgoals in NAIL?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.82-88, March 1988, Austin, Texas, United States [doi>10.1145/308386.308419]
• Ram88: Raghu Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programs. In Robert A. Kowalski and Keneth A. Bowen, editors, Logic Programming: Proceedings of the Fifth International Conference and Symposium, Seattle, Vol 1, pages 140-159, MIT Press, Cambridge, MA, August 1988.
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parallel rewriting systems (e.g., developmental systems, L-systems)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Design, Languages, Management, Performance, Reliability, Theory, Verification