Modular stratification and magic sets for Datalog programs with negation

ABSTRACT

A class of “modularly stratified” logic programs is defined. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible as stratified programs. For modularly stratified programs, the well-founded semantics coincides with the stable model semantics and makes every ground literal true or false. Modularly stratified programs are weakly stratified, but the converse is false. Unlike some weakly stratified programs, modularly stratified programs can be evaluated in a subgoal-at-a time fashion. An extension of top-down methods with memoing that handles this broader class of programs is presented. A technique for rewriting a modularly stratified program for bottom-up evaluation is demonstrated and extended to include magic-set techniques. The rewritten program, when evaluated bottom-up, gives correct answers according to the well-founded semantics, but much more efficiently than computing the complete well-founded model. A one-to-one correspondence between steps of the extended top-down method and steps during the bottom-up evaluation of the magic-rewritten program is exhibited, demonstrating that the complexity of the two methods is the same. Extensions of modular stratification to other operators such as set-grouping and aggregation, which have traditionally been stratified to prevent semantic difficulties, are discussed.

REFERENCES

• 1: ~BALBIN, I., MEENKASHI, K., AND RAMAMOHANARAO, K. 1988. An efficient labelling algorithm for ~magic set computation on stratified databases. Tech. Rep. 88/1. Dept. of Computer Scicncc, ~Univ. of Melbourne, Melbourne, Austraha.
• 2: ~BALBIN, I., PORT, G. S., AND RAMAMOHANARAO, m. 1987. Magic set computation for on stratified ~databases. Tech. Rep. 87/3. Dept. of Computer Science, Univ~ of Melbourne, Melbourne, ~Australia.
• 3: 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]
• 4: 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
• 5: 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]
• 6: 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]
• 7: ~BEERI, C., RAMAKRISHNAN, R., SRIVASTAVA, D., AND SUDARSHAN, S. 1989. Magic implementation ~of stratified logic programs. Manuscript.
• 8: A. Brodsky , Y. Sagiv, Inference of monotonicity constraints in datalog programs, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-199, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73741]
• 9: F. Bry, Logic programming as constructivism: a formalization and its application to databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-50, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73725]
• 10: ~CHAN, D. 1988. Constructive negation based on the completed database. In Proceedings of the ~5th International O)nference and Syrnposiunz on Logic Programming. MIT Press, Cambridge, ~Mass., pp. 111-125.
• 11: ~CHEN, W., KIFER, U., AND WARREN, D. S. 1989. HiLog: A first order semantics for higher-order ~logic programming constructs. In Proceedings of the North American Logic Programming Confel~ ~ence. MIT Press, Cambridge, Mass.
• 12: ~DIETRICH, S. AND WARREN, D. S. 1985. Dynamic programming strategies for the evaluation of ~recursive queries. Tech. Rep. 85/31. Computer Science Dept., State Univ. of New York, Stony ~Brook, N.Y.
• 13: ~GELFOND, M. AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In ~Proceedings of the 5th International Conference and Symposium on Logic Programming. MIT ~Press, Cambridge, Mass., pp. 1070-1080.
• 14: ~KEMP, D. B., AND TOPOR, R. W. 1988. Completeness of a top down query evaluation procedure ~for stratified databases. In Proceedings of the 5th Internattonal ConJerence and Symposium on ~Logic Programming. MIT Press, Cambridge, Mass., pp. 178-194.
• 15: ~KERISIT. J. U. AND PUGIN, J. U. 1988. Efficient query answering on stratified databases. In ~Proceedings of the International Conference on Fifth Generation Computer Systems, pp. 719 726.
• 16: Phokion G. Kolaitis, The expressive power of stratified logic programs, Information and Computation, v.90 n.1, p.50-66, Jan. 1991 [doi>10.1016/0890-5401(91)90059-B]
• 17: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 18: ~PmPPS, G. 1990. Glue: A deductive database programming language. Tech. Rep. TR-CS-90-14. ~Kansas State Univ., Manhattan, Kan., 1990. Also Proceedings of the NACLP'90 Workshop on ~Deductu,e Databases.
• 19: Geoffrey Phipps , Marcia A. Derr , Kenneth A. Ross, Glue-Nail: a deductive database system, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.308-317, May 29-31, 1991, Denver, Colorado, United States
• 20: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• 21: ~PRZYMUSINSKI, T. C. 1989b. On constructive negaUon in logic programming. In Proceedings of ~tile North American Conference on Logic Programming. MIT Press, Cambridge, Mass.
• 22: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 23: H. Przymusinska , T. C. Przymunsinski, Weakly stratified logic programs, Fundamenta Informaticae, v.13 n.1, p.51-65, Mar. 1990
• 24: Raghu Ramakrishnan, Magic templates: a spellbinding approach to logic programs, Journal of Logic Programming, v.11 n.3-4, p.189-216, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90026-L]
• 25: ~I~AMAKRISI-INAN, R,, SRIVASTAVA, D., AND SUDARSHAN, S. 1992. Coral: A deductive database ~programming language. In Proceedings of the 18th International Conference on ~0' La~e ~Databases. VLDB Endowment.
• 26: Raghu Ramakrishnan , Divesh Srivastava, Rule ordering bottom-up fixpoint evaluation of logic programs, Proceedings of the sixteenth international conference on Very large databases, p.359-371, September 1990, Brisbane, Australia
• 27: Kenneth A. Ross, Modular acyclicity and tail recursion in logic programs, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.92-101, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113422]
• 28: 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]
• 29: Kenneth A. Ross, A procedural semantics for well-founded negation in logic programs, Journal of Logic Programming, v.13 n.1, p.1-22, May 1992 [doi>10.1016/0743-1066(92)90019-Y]
• 30: H. Seki, On the power of Alexander templates, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.150-159, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73737]
• 31: ~SEKI, H. AND ITOH, H. 1988. A query evaluation method for stratified programs under the ~extended CWA. In Proceedings of tile 5th International Conference and S)2trq)o3lam otl Logic ~Programming. MIT Press, Cambridge, Mass., pp. 195-211.
• 32: J. D. Ullman, Bottom-up beats top-down for datalog, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.140-149, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73736]
• 33: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 34: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 35: ~VIEILLE, L. 1986. Recursive axioms in deductive databases: The query-subquery approach. In ~Proceedings of the lth International Cotzferetzce orl Ex?ert Databaae Systems.
• 36: ~VmiLLE, L. 1987. A database-complete proof procedure based on SLD-resolunon. In Proceed- ~rags of the 4th International Conference on Logic Programming.

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  F. Theory of Computation
  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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision; Deduction (e.g., natural, rule-based); Logic programming

General Terms:
Algorithms, Languages, Theory

Keywords:
deductive databases, magic sets, modular stratification, rule rewriting, stratification, well-sounded semantics