Fixpoint semantics and optimization of recursive Datalog programs with aggregates*. Issue 5 (23rd August 2017)

• Record Type: Journal Article
• Authors: ZANIOLO, CARLO; YANG, MOHAN; DAS, ARIYAM; SHKAPSKY, ALEXANDER; CONDIE, TYSON; INTERLANDI, MATTEO
• Editors: Rocha, Ricardo; Cao Son, Tran
• Is Part Of: Theory and practice of logic programming. Volume 17:Issue 5/6(2017)
• Page Start: 1048
• Page End: 1065
• Publication Date: 2017-08-23
• Subjects: Datalog, -- Constraints, -- Recursion, -- Aggregates; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068417000436
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: A very desirable Datalog extension investigated by many researchers in the last 30 years consists in allowing the use of the basic SQL aggregatesmin, max, count andsum 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 ofmin ormax in recursive rules does not compromise the declarative fixpoint semantics of the programs using those rules. Then, we revisit the monotonic versions ofcount andsum aggregates proposed by Mazuran et al. (2013b, The VLDB Journal 22, 4, 471–493) and named, respectively, mcount andmsum . 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. In SIGMOD . ACM, 1135–1149) and Datalog-MC (Yang et al . 2017. The VLDB Journal 26, 2, 229–248).