Fixpoint semantics and optimization of recursive Datalog programs with aggregates
From MaRDI portal
Abstract: A very desirable Datalog extension investigated by many researchers in the last thirty years consists in allowing the use of the basic SQL aggregates min, max, count and sum in recursive rules. In this paper, we propose a simple comprehensive solution that extends the declarative least-fixpoint semantics of Horn Clauses, along with the optimization techniques used in the bottom-up implementation approach adopted by many Datalog systems. We start by identifying a large class of programs of great practical interest in which the use of min or max in recursive rules does not compromise the declarative fixpoint semantics of the programs using those rules. Then, we revisit the monotonic versions of count and sum aggregates proposed in (Mazuran et al. 2013b) and named, respectively, mcount and msum. Since mcount, and also msum on positive numbers, are monotonic in the lattice of set-containment, they preserve the fixpoint semantics of Horn Clauses. However, in many applications of practical interest, their use can lead to inefficiencies, that can be eliminated by combining them with max, whereby mcount and msum become the standard count and sum. Therefore, the semantics and optimization techniques of Datalog are extended to recursive programs with min, max, count and sum, making possible the advanced applications of superior performance and scalability demonstrated by BigDatalog (Shkapsky et al. 2016) and Datalog-MC (Yang et al. 2017). This paper is under consideration for acceptance in TPLP.
Recommendations
Cites work
- A Constructive semantic characterization of aggregates in answer set programming
- A declarative extension of horn clauses, and its significance for Datalog and its applications
- Extrema predicates in deductive databases
- How expressive is stratified aggregation?
- scientific article; zbMATH DE number 1024673 (Why is no real title available?)
- Planning as tabled logic programming
- Pushing extrema aggregates to optimize logic queries
- Semantics and complexity of recursive aggregates in answer set programming
- Tabling with answer subsumption: implementation, applications and performance
- The deductive database system [Lscr ][Dscr ][Lscr ]++
- The Semantics of Predicate Logic as a Programming Language
- Vicious circle principle and logic programs with aggregates
- Well-founded and stable semantics of logic programs with aggregates
Cited in
(18)- A decompositional approach for computing least fixed-points of datalog programs with \(\mathcal Z\)-counters
- Recursive rules with aggregation: a simple unified semantics
- A note on fixpoint techniques in data base recursive logic programs
- scientific article; zbMATH DE number 1134643 (Why is no real title available?)
- Scaling-up reasoning and advanced analytics on BigData
- A datalog-based computational model for coordination-free, data-parallel systems
- scientific article; zbMATH DE number 1926634 (Why is no real title available?)
- scientific article; zbMATH DE number 7453122 (Why is no real title available?)
- Modern Datalog Engines
- A Case for Stale Synchronous Distributed Model for Declarative Recursive Computation
- A declarative extension of horn clauses, and its significance for Datalog and its applications
- On Signings and the Well-Founded Semantics
- Parallel Logic Programming: A Sequel
- Efficient iterative programs with distributed data collections
- Aggregate semantics for propositional answer set programs
- Convergence of datalog over (pre-) semirings
- Modern Datalog: concepts, methods, applications (invited paper)
- A semantic approach to optimize linear datalog programs
This page was built for publication: Fixpoint semantics and optimization of recursive Datalog programs with aggregates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592728)
