Modular stratification and magic sets for DATALOG programs with negation

ABSTRACT

We propose a class of programs, called modularly stratified programs that have several attractive properties. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible by 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 all 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. We demonstrate a technique for rewriting a modularly stratified program for bottom-up evaluation and extend this rewriting to include magic-set techniques. The rewritten program, when evaluated bottom-up, gives the same answers as the well-founded semantics. We discuss extending modular stratification to other operators such as set-grouping and aggregation that have traditionally been stratified to prevent semantic difficulties.

REFERENCES

• BMR88: I. Balbin, K. Meenkashi, and K. Ramamohanarao. An efficient labelling algorithm for magic set computation on stratified databases. Technical Report 88/1, Dept. of Computer Science, University of Melbourne, 1988.
• BPR87: I. Balbin, G. Port, and K. Ramamohanarao. Magic set computation for on stratified databases. Technical Report 87/3, Dept. of Computer Science, University of Melbourne, 1987.
• BPRMar: 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]
• BR86: 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
• 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]
• BRSS89: C. Beeri, R. Ramakrishnan, D. Srivastava, and S. Sudarshan. Magic implementation of stratified logic programs. (manuscript), 1989.
• Bry89a: F. Bry, Dec. 1989. (personal communication).
• Bry89b: 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]
• BS89: 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]
• DW85: S. Dietrich and D. S. Warren. Dynamic programming strategies for the evaluation of recursive queries. Technical Report 85/31, Computer Science Department, State University of New York at Stony Brook, 1985.
• GL88: M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. in Proc. Fifth International Conference and Symposium on Logic Programming, 1988.
• Kol87: P.G. Kolaitis. The expressive power of stratified programs. (manuscript), 1987.
• KP88: J.M. Kerisit and j.M. Pugin. Efficient query answering on stratified databases. In Proceedings of the International Conference on Fifth Generation Computer Systems, 1988.
• KT88: D. Kemp and R. Topor. Completeness of a top down query evaluation procedure for stratified databases. In Proc. Fifth international Conference and Symposium on Logic Programming, 1988.
• PP88: H. Przymusinska and T. Przymusinski. Weakly perfect model semantics for logic programs, in Proc. Fifth International Conference and Symposium on Logic Programming, 1988.
• Prz88: 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
• Ram88: R. Ramakrishnan. Magic templates: A spellbinding approach to logic programs. In Proc. Fifth International Conference and Symposium on Logic Programming, 1988.
• Ros89: 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]
• SI88: Hirohisa Seki and Hidenori itoh. A query evaluation method for stratified programs under the extended cwa. In Proc. Fifth International Conference and Symposium on Logic Programming, 1988.
• Ull89a: 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]
• Ull89b: J.D. Ullman. Principles of Database and Knowledge Base Systems. Computer Science Press, Rockville, MD, 1989.
• VGRS88: 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]
• Vie86: L. Vielle. Recursive axioms in deductive databases: The query-subquery approach. In Proc. First International Conference on Expert Database Systems, 1986.
• Vie87: L. Vielle. A database-complete proof procedure based on sld-resolution. In Proc. Fourth International Conference on Logic Programming, 1987.

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Languages, Management, Performance, Theory