{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T02:02:56Z","timestamp":1768701776738,"version":"3.49.0"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2017,8,23]],"date-time":"2017-08-23T00:00:00Z","timestamp":1503446400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A very desirable Datalog extension investigated by many researchers in the last 30 years consists in allowing the use of the basic SQL aggregates <jats:bold>min<\/jats:bold>, <jats:bold>max<\/jats:bold>, <jats:bold>count<\/jats:bold> and <jats:bold>sum<\/jats:bold> 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 <jats:bold>min<\/jats:bold> or <jats:bold>max<\/jats:bold> in recursive rules does not compromise the declarative fixpoint semantics of the programs using those rules. Then, we revisit the monotonic versions of <jats:bold>count<\/jats:bold> and <jats:bold>sum<\/jats:bold> aggregates proposed by Mazuran et al. (2013b, <jats:italic>The VLDB Journal 22<\/jats:italic>, 4, 471\u2013493) and named, respectively, <jats:bold>mcount<\/jats:bold> and <jats:bold>msum<\/jats:bold>. 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 <jats:italic>et al<\/jats:italic>. 2016. In <jats:italic>SIGMOD<\/jats:italic>. ACM, 1135\u20131149) and Datalog-MC (Yang <jats:italic>et al<\/jats:italic>. 2017. <jats:italic>The VLDB Journal 26<\/jats:italic>, 2, 229\u2013248).<\/jats:p>","DOI":"10.1017\/s1471068417000436","type":"journal-article","created":{"date-parts":[[2017,8,23]],"date-time":"2017-08-23T07:08:02Z","timestamp":1503472082000},"page":"1048-1065","source":"Crossref","is-referenced-by-count":31,"title":["Fixpoint semantics and optimization of recursive Datalog programs with aggregates"],"prefix":"10.1017","volume":"17","author":[{"given":"CARLO","family":"ZANIOLO","sequence":"first","affiliation":[]},{"given":"MOHAN","family":"YANG","sequence":"additional","affiliation":[]},{"given":"ARIYAM","family":"DAS","sequence":"additional","affiliation":[]},{"given":"ALEXANDER","family":"SHKAPSKY","sequence":"additional","affiliation":[]},{"given":"TYSON","family":"CONDIE","sequence":"additional","affiliation":[]},{"given":"MATTEO","family":"INTERLANDI","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,8,23]]},"reference":[{"key":"S1471068417000436_ref37","volume-title":"Advanced Database Systems","author":"Zaniolo","year":"1997"},{"key":"S1471068417000436_ref23","doi-asserted-by":"crossref","unstructured":"Shkapsky A. , Yang M. , Interlandi M. , Chiu H. , Condie T. and Zaniolo C. 2016. Big data analytics with Datalog queries on Spark. In Proc. of SIGMOD. ACM, 1135\u20131149.","DOI":"10.1145\/2882903.2915229"},{"key":"S1471068417000436_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57530-8_2"},{"key":"S1471068417000436_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002936"},{"key":"S1471068417000436_ref3","first-page":"52","article-title":"An overview of the LDL system","volume":"10","author":"Chimenti","year":"1987","journal-title":"IEEE Data Engineering Bulletin"},{"key":"S1471068417000436_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321991"},{"key":"S1471068417000436_ref11","unstructured":"Kemp D. B. and Stuckey P. J. 1991. Semantics of logic programs with aggregates. In Proc. of ISLP, 387\u2013401."},{"key":"S1471068417000436_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068402001515"},{"key":"S1471068417000436_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(02)00006-6"},{"key":"S1471068417000436_ref20","unstructured":"Ramakrishnan R. , Srivastava D. and Sudarshan S. 1992. CORAL - control, relations and logic. In Proc. of PVLDB, 238\u2013250."},{"key":"S1471068417000436_ref36","doi-asserted-by":"crossref","unstructured":"Yang M. and Zaniolo C. 2014. Main memory evaluation of recursive queries on multicore machines. In Proc. of IEEE Big Data, 251\u2013260.","DOI":"10.1109\/BigData.2014.7004240"},{"key":"S1471068417000436_ref34","unstructured":"Yang M. , Shkapsky A. and Zaniolo C. 2015. Parallel bottom-up evaluation of logic programs: DeALS on shared-memory multicore machines. In Technical Communications of ICLP."},{"key":"S1471068417000436_ref33","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824052"},{"key":"S1471068417000436_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000222"},{"key":"S1471068417000436_ref1","doi-asserted-by":"crossref","unstructured":"Aref M. et al. 2015. Design and implementation of the LogicBlox system. In Proc. of SIGMOD. ACM, 1371\u20131382.","DOI":"10.1145\/2723372.2742796"},{"key":"S1471068417000436_ref7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1064"},{"key":"S1471068417000436_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536403"},{"key":"S1471068417000436_ref28","unstructured":"Sudarshan S. and Ramakrishnan R. 1991. Aggregation and relevance in deductive databases. In Proc. of VLDB, 501\u2013511."},{"key":"S1471068417000436_ref22","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"S1471068417000436_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"S1471068417000436_ref24","doi-asserted-by":"crossref","unstructured":"Shkapsky A. , Yang M. and Zaniolo C. 2015. Optimizing recursive queries with monotonic aggregates in DeALS. In Proc. of ICDE. IEEE, 867\u2013878.","DOI":"10.1109\/ICDE.2015.7113340"},{"key":"S1471068417000436_ref16","first-page":"264","volume-title":"VLDB","author":"Mumick","year":"1990"},{"key":"S1471068417000436_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.002"},{"key":"S1471068417000436_ref25","doi-asserted-by":"publisher","DOI":"10.14778\/2536274.2536290"},{"key":"S1471068417000436_ref19","unstructured":"Przymusinski T. C. 1988. Perfect model semantics. In Proc. of ICLP\/SLP, 1081\u20131096."},{"key":"S1471068417000436_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2398857.2384645"},{"key":"S1471068417000436_ref27","doi-asserted-by":"crossref","unstructured":"Srivastava D. and Ramakrishnan R. 1992. Pushing constraint selections. In Journal of Logic Programming, 301\u2013315.","DOI":"10.1145\/137097.137897"},{"key":"S1471068417000436_ref10","unstructured":"Kemp D. , Meenakshi K. , Balbin I. and Ramamohanarao K. 1989. Propagating constraints in recursive deductive databases. In North American Conference on Logic Programming, 981\u2013998."},{"key":"S1471068417000436_ref4","volume-title":"Advanced Applications by Least-Fixpoint Algorithms Specified using Aggregates in Datalog","author":"Condie","year":"2017"},{"key":"S1471068417000436_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228882"},{"key":"S1471068417000436_ref9","doi-asserted-by":"crossref","unstructured":"Greco S. , Zaniolo C. and Ganguly S. 1992. Greedy by choice. In Proc. of PODS. ACM, 105\u2013113.","DOI":"10.1145\/137097.137836"},{"key":"S1471068417000436_ref38","unstructured":"Zaniolo C. , Yang M. , Das A. and Interlandi M. 2016. The magic of pushing extrema into recursion: Simple, powerful Datalog programs. In Proc. of AMW."},{"key":"S1471068417000436_ref21","doi-asserted-by":"crossref","unstructured":"Ross K. A. and Sagiv Y. 1992. Monotonic aggregation in deductive databases. In Proc. of PODS, 114\u2013126.","DOI":"10.1145\/137097.137852"},{"key":"S1471068417000436_ref29","doi-asserted-by":"crossref","unstructured":"Swift T. and Warren D. S. 2010. Tabling with answer subsumption: Implementation, applications and performance. In Proc. of JELIA, 300\u2013312.","DOI":"10.1007\/978-3-642-15675-5_26"},{"key":"S1471068417000436_ref39","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000216"},{"key":"S1471068417000436_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"S1471068417000436_ref40","doi-asserted-by":"crossref","unstructured":"Zhou N.-F. , Kameya Y. and Sato T. 2010. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. In Proc. of ICTAI '10. Washington, DC, USA, 213\u2013218.","DOI":"10.1109\/ICTAI.2010.103"},{"key":"S1471068417000436_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0448-z"},{"key":"S1471068417000436_ref15","doi-asserted-by":"crossref","unstructured":"Morris K. A. , Ullman J. D. and Gelder A. V. 1986. Design overview of the NAIL! system. In Proc. of ICLP, 554\u2013568.","DOI":"10.1007\/3-540-16492-8_104"},{"key":"S1471068417000436_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068413000380"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068417000436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T01:50:24Z","timestamp":1555465824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068417000436\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,23]]},"references-count":40,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["S1471068417000436"],"URL":"https:\/\/doi.org\/10.1017\/s1471068417000436","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,23]]}}}