{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:33Z","timestamp":1779174813693,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSf","award":["IIS-1910014"],"award-info":[{"award-number":["IIS-1910014"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.<\/jats:p>","DOI":"10.1145\/3651138","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-19","source":"Crossref","is-referenced-by-count":1,"title":["Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7636-0831","authenticated-orcid":false,"given":"Hangdong","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7714-2195","authenticated-orcid":false,"given":"Austen Z.","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5214-4688","authenticated-orcid":false,"given":"Xiating","family":"Ouyang","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6309-1702","authenticated-orcid":false,"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188938"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_5_1","series-title":"LIPIcs","first-page":"137","volume-title":"CSL","author":"Brault-Baron Johann","year":"2012","unstructured":"Johann Brault-Baron. A negative conjunctive query is easy if and only if it is beta-acyclic. In CSL, volume 16 of LIPIcs, pages 137--151. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2012."},{"key":"e_1_2_1_6_1","unstructured":"Johann Brault-Baron. De la pertinence de l'\u00e9num\u00e9ration : complexit\u00e9 en logiques propositionnelle et du premier ordre. PhD thesis University of Caen Normandy France 2013."},{"key":"e_1_2_1_7_1","volume-title":"Dec","author":"Brault-Baron Johann","year":"2016","unstructured":"Johann Brault-Baron. Hypergraph acyclicity revisited. ACM Comput. Surv., 49(3), Dec 2016."},{"key":"e_1_2_1_8_1","volume-title":"Math. centr. report ZW146","author":"Brouwer Andries E","year":"1980","unstructured":"Andries E Brouwer and Antoon W. J. Kolen. A super-balanced hypergraph has a nest point. Technical report, Math. centr. report ZW146, Amsterdam, 1980."},{"key":"e_1_2_1_9_1","volume-title":"27th International Conference on Database Theory, ICDT 2024, March 25--28, 2024","author":"Capelli Florent","year":"2024","unstructured":"Florent Capelli and Oliver Irwin. Direct access for conjunctive queries with negation. 27th International Conference on Database Theory, ICDT 2024, March 25--28, 2024, Paestum, Italy, pages 13:1--13:20, 2024."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450263"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73848"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000049"},{"key":"e_1_2_1_13_1","series-title":"LIPIcs","first-page":"1","volume-title":"ICALP","author":"Fan Austen Z.","year":"2023","unstructured":"Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In ICALP, volume 261 of LIPIcs, pages 127:1--127:20, 2023."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_15_1","volume-title":"Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851","author":"Grandjean Etienne","year":"2022","unstructured":"Etienne Grandjean and Louis Jachiet. Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR, abs\/2206.13851, 2022."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1974.20"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589298"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2902251.2902280","volume-title":"Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: questions asked frequently. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 13--28. ACM, 2016."},{"key":"e_1_2_1_20_1","first-page":"355","volume-title":"PODS 2021","author":"Lanzinger Matthias","year":"2021","unstructured":"Matthias Lanzinger. Tractability beyond \u00df-acyclicity for conjunctive queries with negation. In PODS 2021, pages 355--369. ACM, 2021."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402147"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129773"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_24_1","first-page":"82","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94. IEEE Computer Society, 1981."},{"key":"e_1_2_1_25_1","first-page":"128","volume-title":"STOC","author":"Chi-Chih Yao Andrew","year":"1982","unstructured":"Andrew Chi-Chih Yao. Space-time tradeoff for answering range queries (extended abstract). In STOC, pages 128--136. ACM, 1982."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214022"},{"key":"e_1_2_1_27_1","volume-title":"Conjunctive queries with negation and aggregation: A linear time characterization. CoRR, abs\/2310.05385","author":"Zhao Hangdong","year":"2023","unstructured":"Hangdong Zhao, Austen Z. Fan, Xiating Ouyang, and Paraschos Koutris. Conjunctive queries with negation and aggregation: A linear time characterization. CoRR, abs\/2310.05385, 2023."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651138","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:03Z","timestamp":1755898803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651138"],"URL":"https:\/\/doi.org\/10.1145\/3651138","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}