{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:57Z","timestamp":1750220697448,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2020,2,25]]},"abstract":"<jats:p>Motivated by applications in declarative data analysis, we study DatalogZ-an extension of Datalog with stratified negation and arithmetics over integers. Reasoning in this language is undecidable, so we present a fragment, called limit DatalogZ, that is powerful enough to naturally capture many important data analysis tasks. In limit DatalogZ, all intensional predicates with a numeric argument are limit predicates that keep only the maximal or minimal bounds on numeric values. Reasoning in limit DatalogZ is decidable if multiplication is used in a way that satisfies our linearity condition. Moreover, fact entailment in limit-linear DatalogZ is \u0394EXP 2 -complete in combined and \u0394P2 -complete in data complexity, and it drops to coNEXP and coNP, respectively, if only (semi-)positive programs are considered. We also propose an additional stability requirement, for which the complexity drops to EXP and P, matching the bounds for usual Datalog. Limit DatalogZ thus provides us with a unified logical framework for declarative data analysis and can be used as a basis for understanding the expressive power of the key data analysis constructs.<\/jats:p>","DOI":"10.1145\/3385658.3385660","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T21:19:34Z","timestamp":1582665574000},"page":"6-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Limit Datalog"],"prefix":"10.1145","volume":"48","author":[{"given":"Bernardo Cuenca","family":"Grau","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"given":"Ian","family":"Horrocks","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"given":"Mark","family":"Kaminski","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"given":"Boris","family":"Motik","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1755913.1755937"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90036-O"},{"key":"e_1_2_1_4_1","first-page":"63","volume-title":"SNAPL","author":"Chin B.","year":"2015"},{"key":"e_1_2_1_5_1","first-page":"1","volume-title":"ICALP","volume":"55","author":"Chistikov D.","year":"2016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90221-E"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"J. Cox K. McAloon and C. Tretkoff. Computational complexity and constraint logic programming languages. Ann. Math. Artif. Intell. 5(2--4):163--189 1992.  J. Cox K. McAloon and C. Tretkoff. Computational complexity and constraint logic programming languages. Ann. Math. Artif. Intell. 5(2--4):163--189 1992.","DOI":"10.1007\/BF01543475"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1064"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer 1999.  N. Immerman. Descriptive Complexity. Springer 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/156"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/259"},{"key":"e_1_2_1_16_1","first-page":"387","volume-title":"ISLP","author":"Kemp D. B.","year":"1991"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733075"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"e_1_2_1_20_1","first-page":"264","volume-title":"VLDB","author":"Mumick I. S.","year":"1990"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1453"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289527"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1053"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2405562"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_27_1","first-page":"501","volume-title":"VLDB","author":"Sudarshan S.","year":"1991"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137854"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824052"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0448-z"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"C. Zaniolo M. Yang A. Das A. Shkapsky T. Condie and M. Interlandi. Fixpoint semantics and optimization of recursive datalog programs with aggregates. Th. Pract. Log. Program. 17(5--6):1048--1065 2017.  C. Zaniolo M. Yang A. Das A. Shkapsky T. Condie and M. Interlandi. Fixpoint semantics and optimization of recursive datalog programs with aggregates. Th. Pract. Log. Program. 17(5--6):1048--1065 2017.","DOI":"10.1017\/S1471068417000436"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385658.3385660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385658.3385660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:49Z","timestamp":1750199569000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385658.3385660"}},"subtitle":["A Declarative Query Language for Data Analysis"],"short-title":[],"issued":{"date-parts":[[2020,2,25]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,2,25]]}},"alternative-id":["10.1145\/3385658.3385660"],"URL":"https:\/\/doi.org\/10.1145\/3385658.3385660","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2020,2,25]]},"assertion":[{"value":"2020-02-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}