{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:01Z","timestamp":1750309441197,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T00:00:00Z","timestamp":1732924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council","award":["714532, 725978"],"award-info":[{"award-number":["714532, 725978"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            We study the complexity of approximating the number of answers to a small query\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            in a large database\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{D}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . We establish an exhaustive classification into tractable and intractable cases if\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is a conjunctive query possibly including disequalities and negations:\n            <jats:list list-type=\"simple\">\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>\n                  If there is a constant bound on the arity of\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  , and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  is bounded.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>\u2014<\/jats:label>\n                <jats:p>\n                  If the arity is unbounded and\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  does not have negations, then the problem has an FPTRAS if and only if the adaptive width of\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varphi\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{NP}=\\mathrm{RP}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , there is no FPRAS even if the treewidth (and the adaptive width) is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).\n          <\/jats:p>","DOI":"10.1145\/3689634","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T12:25:51Z","timestamp":1724415951000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":false,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3159-9418","authenticated-orcid":false,"given":"Marc","family":"Roth","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Queen Mary University of London, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,30]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Foundations of Databases","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. Retrieved from http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_3_2_3_2","volume-title":"Width Functions for Hypertree Decompositions","author":"Adler Isolde","year":"2006","unstructured":"Isolde Adler. 2006. Width Functions for Hypertree Decompositions. Ph.D. Dissertation. Albert-Ludwigs-Universit\u00e4t Freiburg. Retrieved from http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.95.2257&rep=rep1&type=pdf"},{"key":"e_1_3_2_4_2","first-page":"241","volume-title":"Proceedings of the 16th International Conference on Intelligent Systems for Molecular Biology (ISMB),","author":"Alon Noga","year":"2008","unstructured":"Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S\u00fcleyman Cenk Sahinalp. 2008. Biomolecular Network Motif Counting and Discovery by Color Coding. In Proceedings of the 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), 241\u2013249. DOI: 10.1093\/bioinformatics\/btn163"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.1007\/s00224-010-9259-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_6_2","DOI":"10.1145\/3406325.3451014"},{"key":"e_1_3_2_7_2","first-page":"453","volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC \u201902)","volume":"2518","author":"Arvind Vikraman","year":"2002","unstructured":"Vikraman Arvind and Venkatesh Raman. 2002. Approximation Algorithms for Some Parameterized Counting Problems. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC \u201902). Prosenjit Bose and Pat Morin (Eds.), Lecture Notes in Computer Science, Vol. 2518, Springer, 453\u2013464. 10.1007\/3-540-36136-7_40"},{"issue":"2","key":"e_1_3_2_8_2","article-title":"Complexity of Locally-Injective Homomorphisms to Tournaments","volume":"20","author":"Bard Stefan","year":"2018","unstructured":"Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGillivray, and Feiran Yang. 2018. Complexity of Locally-Injective Homomorphisms to Tournaments. Discret. Math. Theor. Comput. Sci. 20, 2 (2018). Retrieved from http:\/\/dmtcs.episciences.org\/4999","journal-title":"Discret. Math. Theor. Comput. Sci"},{"doi-asserted-by":"publisher","key":"e_1_3_2_9_2","DOI":"10.1145\/3389390"},{"key":"e_1_3_2_10_2","first-page":"77","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing","author":"Chandra Ashok K.","year":"1977","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison (Eds.), ACM, New York, NY, 77\u201390. DOI: 10.1145\/800105.803397"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/2902251.2902279","volume-title":"Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201916)","author":"Chen Hubie","year":"2016","unstructured":"Hubie Chen and Stefan Mengel. 2016. Counting Answers to Existential Positive Queries: A Complexity Classification. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201916). Tova Milo and Wang-Chiew Tan (Eds.), ACM, New York, NY, 315\u2013326. DOI: 10.1145\/2902251.2902279"},{"key":"e_1_3_2_12_2","first-page":"2782\u20132789","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI \u201920), the 32nd Innovative Applications of Artificial Intelligence Conference (IAAI \u201920), the 10th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI \u201920)","author":"Cima Gianluca","year":"2020","unstructured":"Gianluca Cima, Maurizio Lenzerini, and Antonella Poggi. 2020. Answering Conjunctive Queries with Inequalities in DL-Lite \\({}_{\\mathcal{R}}\\) . In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI \u201920), the 32nd Innovative Applications of Artificial Intelligence Conference (IAAI \u201920), the 10th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI \u201920). AAAI Press, 2782\u20132789. Retrieved from https:\/\/aaai.org\/ojs\/index.php\/AAAI\/article\/view\/5666"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"Cygan Marek","year":"2015","unstructured":"Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms (1st ed.). Springer Publishing Company, Incorporated.","edition":"1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_2_15_2","first-page":"310","volume-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming - (CP \u201902)","volume":"2470","author":"Dalmau V\u00edctor","year":"2002","unstructured":"V\u00edctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming - (CP \u201902). Pascal Van Hentenryck (Ed.), Lecture Notes in Computer Science, Vol. 2470, Springer, 310\u2013326. DOI: 10.1007\/3-540-46135-3_21"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"2201","DOI":"10.1137\/1.9781611975994.135","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920)","author":"Dell Holger","year":"2020","unstructured":"Holger Dell, John Lapinskas, and Kitty Meeks. 2020. Approximately Counting and Sampling Small Witnesses Using a Colourful Decision Oracle. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA \u201920). Shuchi Chawla (Ed.), SIAM, 2201\u20132211. DOI: 10.1137\/1.9781611975994.135"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.4230\/LIPIcs.ICALP.2019.113"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1007\/978-1-4471-5559-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1007\/s00224-014-9543-y"},{"key":"e_1_3_2_20_2","first-page":"101","article-title":"Random Walks on Combinatorial Objects","author":"Dyer Martin","year":"1999","unstructured":"Martin Dyer and Catherine Greenhill. 1999. Random Walks on Combinatorial Objects. Lond. Math. Soc. Lecture Note Ser. (1999), 101\u2013136.","journal-title":"Lond. Math. Soc. Lecture Note Ser"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1007\/s00453-003-1073-y"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1016\/S0166-218X(00)00387-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1016\/j.cosrev.2008.06.001"},{"key":"e_1_3_2_24_2","first-page":"315","volume-title":"PODS \u201922: Proceedings of the International Conference on Management of Data (PODS \u201922)","author":"Focke Jacob","year":"2022","unstructured":"Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivn\u00fd. 2022. Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. In PODS \u201922: Proceedings of the International Conference on Management of Data (PODS \u201922). Leonid Libkin and Pablo Barcel\u00f3 (Eds.), ACM, new York, 315\u2013324. DOI: 10.1145\/3517804.3526231"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1145\/382780.382783"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1006\/jcss.2001.1809"},{"doi-asserted-by":"publisher","key":"e_1_3_2_27_2","DOI":"10.1145\/1206035.1206036"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1145\/2636918"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1016\/j.websem.2015.06.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.1006\/jcss.2000.1727"},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1016\/0304-3975(86)90174-X"},{"doi-asserted-by":"publisher","unstructured":"Richard M. Karp and Michael Luby. 1983. Monte-Carlo Algorithms for Enumeration and Reliability Problems. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE Computer Society 56\u201364. DOI: 10.1109\/SFCS.1983.35","key":"e_1_3_2_32_2","DOI":"10.1109\/SFCS.1983.35"},{"doi-asserted-by":"publisher","key":"e_1_3_2_33_2","DOI":"10.1007\/s00224-016-9684-2"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/3196959.3196982","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Koutris Paraschos","year":"2018","unstructured":"Paraschos Koutris and Jef Wijsen. 2018. Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Jan Van den Bussche and Marcelo Arenas (Eds.), ACM, New York, NY, 209\u2013224. DOI: 10.1145\/3196959.3196982"},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.1145\/1721837.1721845"},{"doi-asserted-by":"publisher","key":"e_1_3_2_36_2","DOI":"10.4086\/toc.2010.v006a005"},{"doi-asserted-by":"publisher","key":"e_1_3_2_37_2","DOI":"10.1007\/s00224-009-9248-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_38_2","DOI":"10.1145\/2535926"},{"doi-asserted-by":"publisher","key":"e_1_3_2_39_2","DOI":"10.1016\/j.dam.2015.06.019"},{"doi-asserted-by":"publisher","key":"e_1_3_2_40_2","DOI":"10.1006\/jcss.1999.1626"},{"doi-asserted-by":"publisher","key":"e_1_3_2_41_2","DOI":"10.1016\/j.jcss.2013.01.012"},{"doi-asserted-by":"publisher","key":"e_1_3_2_42_2","DOI":"10.1016\/0095-8956(84)90013-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_43_2","DOI":"10.1007\/s00453-021-00805-y"},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1016\/j.ipl.2014.02.012"},{"key":"e_1_3_2_45_2","first-page":"322","volume-title":"Proceedings of the 3rd International Colloquium on Automata, Languages and Programming","author":"Schnorr Claus-Peter","year":"1976","unstructured":"Claus-Peter Schnorr. 1976. Optimal Algorithms for Self-Reducible Problems. In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming. S. Michaelson and Robin Milner (Eds.), Edinburgh University Press, 322\u2013337."},{"key":"e_1_3_2_46_2","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Proceedings of the 7th International Conference on Very Large Data Bases. IEEE Computer Society, 82\u201394."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:47Z","timestamp":1750295387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,30]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3689634"],"URL":"https:\/\/doi.org\/10.1145\/3689634","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,11,30]]},"assertion":[{"value":"2022-03-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}