Monotonic aggregation in deductive databases

ABSTRACT

We propose a semantics for aggregates in deductive databases based on a notion of minimality. Unlike some previous approaches, we form a minimal model of a program component including aggregate operators, rather than insisting that the aggregate apply to atoms that have been fully determined, or that aggregate functions are rewritten in terms of negation. In order to guarantee the existence of such a minimal model we need to insist that the domains over which we are aggregating are complete lattices, and that the program is in a sense monotonic. Our approach generalizes previous approaches based on the well-founded semantics and various forms of stratification. We are also able to handle a large variety of monotonic (or pseudo-monotonic) aggregate functions.

REFERENCES

• AH88: Serge Abiteboul , Richard Hull, Data functions, datalog and negation, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.143-153, June 01-03, 1988, Chicago, Illinois, United States
• CGT90: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• GGZ91: Sumit Ganguly , Sergio Greco , Carlo Zaniolo, Minimum and maximum predicates in logic programming, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-163, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113427]
• GL88: M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. Fifth International Conference and Symposium on Logic Programming, 1988.
• KS91: D.B. Kemp and P. J. Stuckey. Semantics of logic programs with aggregates. In Proceedings of the International Logic Programming Symposium, 1991.
• MPR90: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• Ros90: 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]
• SR91: S. Sudarshan , Raghu Ramakrishnan, Aggregation and Relevance in Deductive Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.501-511, September 03-06, 1991
• Tar55: A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific J. Math., 5:285-309, 1955.
• VG92a: 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]
• VG92b: Allen Van Gelder, The well-founded semantics of aggregation, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.127-138, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137854]
• VGRS91: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Theory