Monotonic Aggregation in Deductive Databases.

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

@inproceedings{DBLP:conf/pods/RossS92,
  author    = {Kenneth A. Ross and
               Yehoshua Sagiv},
  title     = {Monotonic Aggregation in Deductive Databases},
  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     = {114-126},
  ee        = {http://doi.acm.org/10.1145/137097.137852, db/conf/pods/RossS92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

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/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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/...

BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1211 KB]

Journal Version

Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Database. J. Comput. Syst. Sci. 54(1): 79-97(1997) BibTeX

References

[AH88]: Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153 BibTeX
[CGT90]: Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
BibTeX
[GGZ91]: Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163 BibTeX
[GL88]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[KS91]: David B. Kemp, Peter J. Stuckey: Semantics of Logic Programs with Aggregates. ISLP 1991: 387-401 BibTeX
[MPR90]: Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX
[Ros90]: Kenneth A. Ross: Modular Stratification and Magic Sets for Datalog Programs with Negation. J. ACM 41(6): 1216-1266(1994) BibTeX
[SR91]: S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511 BibTeX
[Tar55]: ...
[VG92a]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. J. Comput. Syst. Sci. 47(1): 185-221(1993) BibTeX
[VG92b]: Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138 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

David B. Kemp, Kotagiri Ramamohanarao: Efficient Recursive Aggregation and Negation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 10(5): 727-745(1998)
Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]