On the power of magic

ABSTRACT

This paper considers the efficient evaluation of recursive queries expressed using Horn Clauses. We define sideways information passing formally and show how a query evaluation algorithm may be defined in terms of sideways information passing and control. We then consider a class of information passing strategies which suffices to describe most query evaluation algorithms in the database literature, and show that these strategies may always be implemented by rewriting a given program and evaluating the rewritten program bottom-up. We describe in detail several algorithms for rewriting a program. These algorithms generalize the Counting and Magic Sets algorithms to work with arbitrary programs. Safety and optimality of the algorithms are also considered.

REFERENCES

• Bancilhon et al 86: 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]
• Bancilhon and Ramakrishnan 86a: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• Bancilhon and Ramakrishnan 86b: "Performance Evaluation of Data Intensive Logic Programs," F Bancllhon and R Ramakmhnan, Preprmts of Workshop on Foundations of Deductive Databases and Logic Progranmung, Washington, D C, Aug ust 1986,
• Beeri et al 87: C. Beeri , S. Naqvi , R. Ramakrishnan , O. Shmueli , S. Tsur, Sets and negation in a logic data base language (LDL1), Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.21-37, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28662]
• Henschen and Naqvi 84: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• Kifer and Lozinskii 85: "Query Opumtzauon m Logm Databases," M Kffer and E Lozanskn, Techmcal Report, SUNY at Stonybrook, June 1985
• Kifer and Lozinskii 86: " A Framework for an Efficient ImplementaUon of Deducuve Databases," M gafer and E Lozanskn, Proc Advanced Database Symposium, Tokyo, 1986
• Lloyd 84: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• Lozinskii 85: "Evaluaung Queries m Deductive Databases by Generattng," E Lozmskn, Proc 11th internatwnal Joint Conference on Arttfictal lntelhgence, 1985
• McKay and Shapiro 81: "Using Aclave Conneclaon Graphs for Reasonmg with Recurslve Rules," D McKay and S Shapn'o, Proc 7th lnternatwnal Joint Conference on Artificial Intelhgence, 1981
• Rohmer and Lescoeur 85: "La Methode Alexandre une soluuon pour trmter les axlomes reeursffs darts les bases de donnees deduclaves ," Rohmer and Lescoeur, Colloque Reconnatssance de Formes et lntelhgence Art~ctelle, Grenoble, November 1985
• Sacca and Zaniolo 86a: Domenico Saccà , Carlo Zaniolo, On the implementation of a simple class of logic queries for databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.16-23, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6013]
• Sacca and Zaniolo 86b: Domenico Saccá , Carlo Zaniolo, The generalized counting method for recursive logic queries, Proceedings on International conference on database theory, p.31-53, December 1986, Rome, Italy
• Ullman 85: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• Van Gelder 86: "A Message Passmg Framework for Recurslve Query Evaluauon," A. Van Gelder, Proc SIG- MOD, 1986
• Vieille 86: "Recurswe axioms m DeAucuve Databases The Query/Subquery Approach," L Vletlle, Proc Fwst Intl Conference on Expert Database Systents, Charleston, 1986

INDEX TERMS

Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Management, Performance, Theory, Verification