{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:30Z","timestamp":1750220490122,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,22]],"date-time":"2021-12-22T00:00:00Z","timestamp":1640131200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n            Motivated by applications in declarative data analysis, in this article, we study\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            \u2014an extension of Datalog with stratified negation and arithmetic functions over integers. This language is known to be undecidable, so we present the fragment of\n            <jats:italic>limit<\/jats:italic>\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            programs, which is powerful enough to naturally capture many important data analysis tasks. In limit\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            , all intensional predicates with a numeric argument are\n            <jats:italic>limit<\/jats:italic>\n            predicates that keep maximal or minimal bounds on numeric values. We show that reasoning in limit\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            is decidable if a\n            <jats:italic>linearity<\/jats:italic>\n            condition restricting the use of multiplication is satisfied. In particular, limit-linear\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            is complete for \u0394\n            <jats:sub>2<\/jats:sub>\n            <jats:sup>EXP<\/jats:sup>\n            and captures \u0394\n            <jats:sub>2<\/jats:sub>\n            <jats:sup>P<\/jats:sup>\n            over ordered datasets in the sense of descriptive complexity. We also provide a comprehensive study of several fragments of limit-linear\n            <jats:italic>Datalog<\/jats:italic>\n            <jats:sub>Z<\/jats:sub>\n            . We show that semi-positive limit-linear programs (i.e., programs where negation is allowed only in front of extensional atoms) capture coNP over ordered datasets; furthermore, reasoning becomes coNEXP-complete in combined and coNP-complete in data complexity, where the lower bounds hold already for negation-free programs. In order to satisfy the requirements of data-intensive applications, we also propose an additional stability requirement, which causes the complexity of reasoning to drop to EXP in combined and to P in data complexity, thus obtaining the same bounds as for usual Datalog. Finally, we compare our formalisms with the languages underpinning existing Datalog-based approaches for data analysis and show that core fragments of these languages can be encoded as limit programs; this allows us to transfer decidability and complexity upper bounds from limit programs to other formalisms. Therefore, our article provides a unified logical framework for declarative data analysis which can be used as a basis for understanding the impact on expressive power and computational complexity of the key constructs available in existing languages.\n          <\/jats:p>","DOI":"10.1145\/3495009","type":"journal-article","created":{"date-parts":[[2021,12,22]],"date-time":"2021-12-22T19:10:35Z","timestamp":1640200235000},"page":"1-83","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity and Expressive Power of Limit Datalog"],"prefix":"10.1145","volume":"69","author":[{"given":"Mark","family":"Kaminski","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8886-6129","authenticated-orcid":false,"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, UK and Department of Informatics, University of Oslo, Oslo, Norway"}]},{"given":"Bernardo Cuenca","family":"Grau","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]},{"given":"Boris","family":"Motik","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]},{"given":"Ian","family":"Horrocks","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,12,22]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1755913.1755937"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1237975"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/61352.61354"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90036-O"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137115"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90037-7"},{"key":"e_1_3_4_9_2","first-page":"63","volume-title":"SNAPL","author":"Chin Brian","year":"2015","unstructured":"Brian Chin, Daniel von Dincklage, Vuk Ercegovac, Peter Hawkins, Mark S. Miller, Franz Josef Och, Christopher Olston, and Fernando Pereira. 2015. Yedalog: Exploring knowledge at scale. In SNAPL. Thomas Ball, Rastislav Bod\u00edk, Shriram Krishnamurthi, Benjamin S. Lerner, and Greg Morrisett (Eds.), Vol. 32. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 63\u201378. DOI: https:\/\/doi.org\/10.4230\/LIPIcs.SNAPL.2015.63"},{"key":"e_1_3_4_10_2","first-page":"128:1\u2013128:13","volume-title":"ICALP","author":"Chistikov Dmitry","year":"2016","unstructured":"Dmitry Chistikov and Christoph Haase. 2016. The taming of the semi-linear set. In ICALP. Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 128:1\u2013128:13. DOI: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.128"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/308386.308416"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/161982.161992"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1979.82.43"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01543475"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.2.213"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_11"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/646398.691169"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.002"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1064"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00057-8"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90136-3"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8_3"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/647849.737051"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00194-6"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603092"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.001"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_4_31_2","first-page":"2862","volume-title":"AAAI","author":"Kaminski Mark","year":"2020","unstructured":"Mark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, and Ian Horrocks. 2020. Complexity and expressive power of disjunction and negation in limit Datalog. In AAAI. AAAI Press, 2862\u20132869. DOI: https:\/\/doi.org\/10.1609\/aaai.v34i03.5676"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171802"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3304889.3304919"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/2875343.2875346"},{"key":"e_1_3_4_36_2","first-page":"387","volume-title":"ISLP","author":"Kemp David B.","year":"1991","unstructured":"David B. Kemp and Peter J. Stuckey. 1991. Semantics of logic programs with aggregates. In ISLP. Vijay A. Saraswat and Kazunori Ueda (Eds.). MIT Press, 387\u2013401."},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683260"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733075"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585518"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2893896"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/645916.671834"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3322276.3322287"},{"key":"e_1_3_4_45_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90068-0"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1453"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289527"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1053"},{"issue":"4","key":"e_1_3_4_52_2","first-page":"423","article-title":"Complexity of Presburger arithmetic with fixed quantifier dimension","volume":"30","author":"Sch\u00f6ning Uwe","year":"1997","unstructured":"Uwe Sch\u00f6ning. 1997. Complexity of Presburger arithmetic with fixed quantifier dimension. Theory Comput. Sci. 30, 4 (1997), 423\u2013428. DOI: https:\/\/doi.org\/10.1007\/BF02679468","journal-title":"Theory Comput. Sci."},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2012.6378643"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2405562"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.5555\/647843.736424"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/645917.672148"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.5555\/187812.187977"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)10008-5"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137854"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0500555-0"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824052"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0448-z"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000436"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3495009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:49:19Z","timestamp":1750193359000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,22]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3495009"],"URL":"https:\/\/doi.org\/10.1145\/3495009","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,12,22]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}