2017/07/18 by Carlo Zaniolo, Mohan Yang, Zaniolo, Carlo +9
Computer Science · #Advanced Database Systems and Queries #Databases (cs.DB) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1707.05681
openalex publication_date 2017/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A very desirable Datalog extension investigated by many researchers in the\nlast thirty years consists in allowing the use of the basic SQL aggregates min,\nmax, count and sum in recursive rules. In this paper, we propose a simple\ncomprehensive solution that extends the declarative least-fixpoint semantics of\nHorn Clauses, along with the optimization techniques used in the bottom-up\nimplementation approach adopted by many Datalog systems. We start by\nidentifying a large class of programs of great practical interest in which the\nuse of min or max in recursive rules does not compromise the declarative\nfixpoint semantics of the programs using those rules. Then, we revisit the\nmonotonic versions of count and sum aggregates proposed in (Mazuran et al.\n2013b) and named, respectively, mcount and msum. Since mcount, and also msum on\npositive numbers, are monotonic in the lattice of set-containment, they\npreserve the fixpoint semantics of Horn Clauses. However, in many applications\nof practical interest, their use can lead to inefficiencies, that can be\neliminated by combining them with max, whereby mcount and msum become the\nstandard count and sum. Therefore, the semantics and optimization techniques of\nDatalog are extended to recursive programs with min, max, count and sum, making\npossible the advanced applications of superior performance and scalability\ndemonstrated by BigDatalog (Shkapsky et al. 2016) and Datalog-MC (Yang et al.\n2017). This paper is under consideration for acceptance in TPLP.\n