An alternating fixpoint tailored to magic programs

ABSTRACT

We study applying the magic-sets transformation technique to Datalog programs with negation that may not have 2-valued well-founded models. In this general setting we encounter the problem that the well-founded model of the original program does not always agree with the well-founded model of the magic program derived by commonly used left-to-right sips on the query. In order to fix this disagreement we present a novel method that is obtained by slightly and naturally tailoring Van Gelder's alternating fixpoint technique [16] to a magic program.

REFERENCES

• 1: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 2: I. Balbin , G. S. Port , K. Ramamohanarao , K. Meenakshi, Efficient bottom-up computation of queries on stratified databases, Journal of Logic Programming, v.11 n.3-4, p.295-344, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90030-S]
• 3: 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]
• 4: Chen, W. and D.S. Warren {1992}. "A go#loriented #pproach to computing the well founded semantics," Proc. of Joint Intl. Conf. and Symp. on Logic Programming.
• 5: Marcia A. Derr , Shinichi Morishita , Geoffrey Phipps, Design and implementation of the glue-nail database system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.147-156, May 25-28, 1993, Washington, D.C., United States
• 6: Kerisit, J.M. and J.M. Pugin {1988}. "Efficient query answering on stratified databases," Proc. of Intl. Conf. on Fifth Generation Computer Systems, pp. 719-726.
• 7: Kemp, D.B., P.J. Stuckey and D. Srivastava {1991}. "Magic sets and bottom-up evaluation of wellfounded models," Proc. of Intl. Logic Programming Syrup., pp.337-351.
• 8: Kemp, D.B., P.J. Stuckey and D. Srivastava {1992}. "Query restricted bottom-up evaluation of normal logic programs," Proc. of Joint Intl. Conf. and Syrup. on Logic Programming
• 9: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 10: Ramakrishnan, R., D. Srivastava and S. Sudarshan {1992}. "Controlling the search in bottom-up evaluation," Proc. of Joint Intl. Conf. and Syrup. on Logic Programming
• 11: K. A. Ross, A procedural semantics for well founded negation in logic programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.22-33, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73724]
• 12: Kenneth A. Ross, Modular stratification and magic sets for DATALOG programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298558]
• 13: Yehoshua Sagiv, Is there anything better than magic, Proceedings of the 1990 North American conference on Logic programming, p.235-254, January 1990, Austin, Texas, United States
• 14: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 15: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]
• 16: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

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

General Terms:
Algorithms, Languages, Performance