Article

Free access

Monotonic aggregation in deductive databases

Authors:

Kenneth A. Ross,

Yehoshua SagivAuthors Info & Claims

PODS '92: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 114 - 126

https://doi.org/10.1145/137097.137852

Published: 01 July 1992 Publication History

PDF eReader

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

[1]

S. Abiteboul and R. Hull. Data functions, Datalog and negation. In Proceedings of the A CM-SIGMOD international Conference on Management of Data, pages 143-153, 1988.

Digital Library

Google Scholar

[2]

S. Ceri, G. Gottlob, and L. Tanca. Logic Programming and Databases. Springer- Verlag, 1990.

Digital Library

Google Scholar

[3]

S. Ganguly, S. Greco, and C. Zaniolo. Minimum and maximum predicates in deductive databases. In Proceedings of the Tenth A CM Symposium on Principles of Database Systems, 1991.

Digital Library

Google Scholar

[4]

M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. Fifth International Conference and Symposium on Logic Programming, 1988.

Google Scholar

[5]

D.B. Kemp and P. J. Stuckey. Semantics of logic programs with aggregates. In Proceedings of the International Logic Programming Symposium, 1991.

Google Scholar

[6]

I.S. Mumick, H. Pirahesh, and R. Ramakrishnan. The magic of duplicates and aggregates. In Proceedings of the International Conference on Very Large Databases, 1990.

Digital Library

Google Scholar

[7]

K.A. Ross. Modular stratification and magic sets for Datalog programs with negation. In Proceedings of the Ninth A CM Symposium on Principles of Database Systems, 1990. Full version submitted for journal publication.

Digital Library

Google Scholar

[8]

S. Sudarshan and R. Ramakrishnan. Aggregation and relevance in deductive databases. In Proceedings of the International Conference on Very Large Databases, 1991.

Digital Library

Google Scholar

[9]

A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific J. Math., 5:285-309, 1955.

Crossref

Google Scholar

[10]

A. Van Gelder. The alternating fixpoint of logic programs with negation. Journal of Computer and System Sciences, 1992. Abstract appeared in Eighth ACM Symposium on Principles of Database Systems, 1989.

Digital Library

Google Scholar

[11]

A. Van Gelder. The well-founded semantics of aggregation, in Proc. Eleventh A CM Symposium on Principles of Database Systems, 1992.

Digital Library

Google Scholar

[12]

A. Van Gelder, K. A. Ross, and J. S. Schlipfi Unfounded sets and wellfounded semantics for general logic programs. YACM, 38(3):620-650, 1991.

Digital Library

Google Scholar

Cited By

View all

Abo Khamis MNgo HPichler RSuciu DWang Y(2024)Convergence of datalog over (Pre-) SemiringsJournal of the ACM10.1145/364302771:2(1-55)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3643027
Shaikhha ASuciu DSchleich MNgo H(2024)Optimizing Nested Recursive QueriesProceedings of the ACM on Management of Data10.1145/36392712:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639271
Sahebolamri ABarrett LMoore SMicinski K(2023)Bring Your Own Data Structures to DatalogProceedings of the ACM on Programming Languages10.1145/36228407:OOPSLA2(1198-1223)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622840
Show More Cited By

Index Terms

Monotonic aggregation in deductive databases

Recommendations

Monotonic Aggregation in Deductive Databases
Special issue: dedicated to the memory of Paris Kanellakis

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 ...
Using clausal deductive databases for defining semantics in disjunctive deductive databases

This paper investigates the novel concept of i>clausal deductive databases (cd-databases), which are special normal deductive databases - i.e., deductive databases which may contain default negation in rule bodies - over a typed meta-language i>L^...
Clausal Deductive Databases and a General Framework for Semantics in Disjunctive Deductive Databases
FoIKS '00: Proceedings of the First International Symposium on Foundations of Information and Knowledge Systems

In this paper we will investigate the novel concept of clausal deductive databases (cd-databases), which are special normal deductive databases - i.e. deductive databases which may contain default negation in rule bodies - over a meta-language L^cd with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '92: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

July 1992

392 pages

ISBN:0897915194

DOI:10.1145/137097

Chairmen:
Moshe Y. Vardi
IBM Almaden Research Center
,
Paris C. Kanellakis
Brown Univ., Providence, RI

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS92

Sponsor:

SIGMOD/PODS92: SIGMOD/PODS '92

June 2 - 5, 1992

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
575
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)12

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Abo Khamis MNgo HPichler RSuciu DWang Y(2024)Convergence of datalog over (Pre-) SemiringsJournal of the ACM10.1145/364302771:2(1-55)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3643027
Shaikhha ASuciu DSchleich MNgo H(2024)Optimizing Nested Recursive QueriesProceedings of the ACM on Management of Data10.1145/36392712:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639271
Sahebolamri ABarrett LMoore SMicinski K(2023)Bring Your Own Data Structures to DatalogProceedings of the ACM on Programming Languages10.1145/36228407:OOPSLA2(1198-1223)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622840
Zhang YWang YFlatt OCao DZucker PRosenthal ETatlock ZWillsey M(2023)Better Together: Unifying Datalog and Equality SaturationProceedings of the ACM on Programming Languages10.1145/35912397:PLDI(468-492)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591239
Sun YKumar SGilray TMicinski K(2023)Communication-Avoiding Recursive Aggregation2023 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER52292.2023.00024(197-208)Online publication date: 31-Oct-2023
https://doi.org/10.1109/CLUSTER52292.2023.00024
Khamis MNgo HPichler RSuciu DRemy Wang Y(2022)Datalog in WonderlandACM SIGMOD Record10.1145/3552490.355249251:2(6-17)Online publication date: 29-Jul-2022
https://dl.acm.org/doi/10.1145/3552490.3552492
Liu YStoller S(2022)Recursive Rules with Aggregation: A Simple Unified SemanticsLogical Foundations of Computer Science10.1007/978-3-030-93100-1_11(156-179)Online publication date: 10-Jan-2022
https://dl.acm.org/doi/10.1007/978-3-030-93100-1_11
Szabó TErdweg SBergmann GFreund SYahav E(2021)Incremental whole-program analysis in Datalog with latticesProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454026(1-15)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454026
Wang JWu JLi MGu JDas AZaniolo C(2021)Formal semantics and high performance in declarative machine learning using DatalogThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00665-630:5(859-881)Online publication date: 31-May-2021
https://dl.acm.org/doi/10.1007/s00778-021-00665-6
Szabó TBergmann GErdweg SVoelter M(2020)Proceedings 36th International Conference on Logic Programming (Technical Communications)Electronic Proceedings in Theoretical Computer Science10.4204/EPTCS.325.35325(280-281)Online publication date: 19-Sep-2020
https://doi.org/10.4204/EPTCS.325.35
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Monotonic Aggregation in Deductive Databases

Using clausal deductive databases for defining semantics in disjunctive deductive databases

Clausal Deductive Databases and a General Framework for Semantics in Disjunctive Deductive Databases