The Well-Founded Semantics of Aggregation.

@inproceedings{DBLP:conf/pods/Gelder92,
  author    = {Allen Van Gelder},
  title     = {The Well-Founded Semantics of Aggregation},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {127-138},
  ee        = {http://doi.acm.org/10.1145/137097.137854, db/conf/pods/Gelder92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AV91]

Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX

[BRSS92]

Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104 BibTeX

[CM90]

Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394 BibTeX

[GGZ91]

Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163 BibTeX

[GS86]

...

[Imm86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[KKR90]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX

[KS91]

David B. Kemp, Peter J. Stuckey: Semantics of Logic Programs with Aggregates. ISLP 1991: 387-401 BibTeX

[Kun88]

Kenneth Kunen: Some Remarks on the Completed Database. ICLP/SLP 1988: 978-992 BibTeX

[LT84]

John W. Lloyd, Rodney W. Topor: Making Prolog more Expressive. J. Log. Program. 1(3): 225-240(1984) BibTeX

[Mos74]

...

[MPR90]

Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX

[RS92]

Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Databases. PODS 1992: 114-126 BibTeX

[SR91]

S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511 BibTeX

[VG92]

Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. J. Comput. Syst. Sci. 47(1): 185-221(1993) BibTeX

[VGRS91]

Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991) BibTeX

Referenced by

1. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
2. Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Databases. PODS 1992: 114-126
3. Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104