The well-founded semantics of aggregation

ABSTRACT

Common aggregation predicates have natural definitions in logic, either as first order sentences (min, max, etc.), or with elementary induction over a data structure that represents the relation (sum, count, etc.). The well-founded semantics for logic programs provides an interpretation of such definitions. The interpretation of first-order aggregates seems to be quite natural and intuitively satisfying, even in the presence of recursion through aggregation. Care is needed to get useful results on inductive aggregates, however. A basic building block is the “subset” predicate, which states that a data structure represents a subset of an IDB predicate, and which is definable in the well-founded semantics. The analogous “superset” is also definable, and their combination yields a “generic” form of findall. Surprisingly, findall must be used negatively to obtain useful approximations when the exact relation is not yet known. Extensions to the semantics, restrictions on the input, and other supplementary requirements proposed in earlier studies appear to be unnecessary for the purpose of attaching a meaning to a program that involves recursion through aggregation. For example, any reasonable definition of “shortest paths” tolerates negative weight edges, correctly computes shortest paths that exist, and leave tuples undefined where negative-weight cycles cause the shortest path not to exist. Other examples exhibit similarly robust behavior, when defined carefully. Connections with the generic model of computation are discussed briefly.

REFERENCES

• AV91: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• BRSS92: Catriel Beeri , Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, The valid model semantics for logic programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.91-104, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137115]
• CM90: Mariano P. Consens , Alberto O. Mendelzon, Low complexity aggregation in GraphLog and Datalog, Proceedings of the third international conference on database theory on Database theory, p.379-394, November 1990, Paris, France
• 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]
• GS86: Y. Gure vich and S. Shelah. Fixed-point extensions of first order logic. Annals of Pure and Applied Logic, 32:265-280, 1986.
• Imm86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• KKR90: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• KS91: D.B. Ke mp and P. J. Stuckey. Semantics of logic programs with aggregates. In International Logic Programming Symposium, pages 387-401, 1991.
• Kun88: K. Kunen. Some remarks on the completed database. Technical Report 775, Univ. of Wisconsin, Madison, WI 53706, 1988. (Abstract appeared in 5th Int'l Conf. Syrup. on Logic Programming, Seattle, Aug. 1988).
• LT84: J.W. Lloyd and R. W. Topor. Making Prolog more expressive. Journal of Logic Programming, 1(3):225-240, 1984.
• Mos74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• 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
• RS92: Kenneth A. Ross , Yehoshua Sagiv, Monotonic aggregation in deductive databases, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.114-126, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137852]
• 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
• VG92: Allen Van Gelder, The alternating fixpoint of logic programs with negation, Selected papers of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.185-221, August 1993, Philadelphia, Pennsylvania, United States
• 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.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  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.1 Logical Design
          Subjects: Data models
      H.2.3 Languages

          Nouns: Prolog

General Terms:
Languages, Theory