{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T22:19:02Z","timestamp":1790288342895,"version":"4.1.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,24]],"date-time":"2016-02-24T00:00:00Z","timestamp":1456272000000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,4,7]]},"abstract":"<jats:p>This article charts the tractability frontier of two classes of relational algebra queries in tuple-independent probabilistic databases. The first class consists of queries with join, projection, selection, and negation but without repeating relation symbols and union. The second class consists of quantified queries that express the following binary relationships among sets of entities: set division, set inclusion, set equivalence, and set incomparability. Quantified queries are expressible in relational algebra using join, projection, nested negation, and repeating relation symbols.<\/jats:p>\n          <jats:p>Each query in the two classes has either polynomial-time or #P-hard data complexity and the tractable queries can be recognised efficiently. Our result for the first query class extends a known dichotomy for conjunctive queries without self-joins to such queries with negation. For quantified queries, their tractability is sensitive to their outermost projection operator: They are tractable if no attribute representing set identifiers is projected away and #P-hard otherwise.<\/jats:p>","DOI":"10.1145\/2877203","type":"journal-article","created":{"date-parts":[[2016,2,26]],"date-time":"2016-02-26T14:29:03Z","timestamp":1456496943000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Dichotomies for Queries with Negation in Probabilistic Databases"],"prefix":"10.1145","volume":"41","author":[{"given":"Robert","family":"Fink","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,2,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley , Reading, MA . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350250"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745760"},{"key":"e_1_2_1_5_1","volume-title":"Estevam Junior Hruschka, and Tom Mitchell","author":"Carlson Andrew","year":"2010","unstructured":"Andrew Carlson , Justin Betteridge , Bryan Kisiel , Burr Settles , Estevam Junior Hruschka, and Tom Mitchell . 2010 . Toward an architecture for never-ending language learning. In AAAI. Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam Junior Hruschka, and Tom Mitchell. 2010. Toward an architecture for never-ending language learning. In AAAI."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Nilesh Dalvi and Dan Suciu. 2004. Efficient query evaluation on probabilistic databases. In VLDB 864--875.   Nilesh Dalvi and Dan Suciu. 2004. Efficient query evaluation on probabilistic databases. In VLDB 864--875.","DOI":"10.1016\/B978-012088469-8.50076-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_10_1","unstructured":"Guy Van den Broeck. 2011. On the completeness of first-order knowledge compilation for lifted probabilistic inference. In NIPS. 1386--1394.  Guy Van den Broeck. 2011. On the completeness of first-order knowledge compilation for lifted probabilistic inference. In NIPS. 1386--1394."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623623"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140445"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0310-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594549"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767912"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.295124"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_18_1","volume-title":"Guy Van den Broeck, and Dan Suciu","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff , Guy Van den Broeck, and Dan Suciu . 2014 a. Understanding the complexity of lifted inference and asymmetric weighted model counting. In UAI. 280--289. Eric Gribkoff, Guy Van den Broeck, and Dan Suciu. 2014a. Understanding the complexity of lifted inference and asymmetric weighted model counting. In UAI. 280--289."},{"key":"e_1_2_1_19_1","first-page":"6","article-title":"Lifted probabilistic inference: A guide for the database researcher","volume":"37","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff , Dan Suciu , and Guy Van den Broeck . 2014 b. Lifted probabilistic inference: A guide for the database researcher . IEEE Data Eng. Bull. 37 , 3 (2014), 6 -- 17 . Eric Gribkoff, Dan Suciu, and Guy Van den Broeck. 2014b. Lifted probabilistic inference: A guide for the database researcher. IEEE Data Eng. Bull. 37, 3 (2014), 6--17.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9137-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559984"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274603"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.14778\/3402707.3402741","article-title":"Queries with difference on probabilistic databases","volume":"4","author":"Khanna Sanjeev","year":"2011","unstructured":"Sanjeev Khanna , Sudeepa Roy , and Val Tannen . 2011 . Queries with difference on probabilistic databases . Proc. VLDB 4 , 11 (2011), 1051 -- 1062 . Sanjeev Khanna, Sudeepa Roy, and Val Tannen. 2011. Queries with difference on probabilistic databases. Proc. VLDB 4, 11 (2011), 1051--1062.","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559887"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.61"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Ralf Rantzau. 2004. Frequent itemset discovery with SQL using universal quantification. In Database Support Data Mining Appl. 194--213.  Ralf Rantzau. 2004. Frequent itemset discovery with SQL using universal quantification. In Database Support Data Mining Appl. 194--213.","DOI":"10.1007\/978-3-540-44497-8_10"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233334"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0151-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool Publishers.   Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_39_1","unstructured":"Ting-You Wang Christopher R\u00e9 and Dan Suciu. 2008. Implementing NOT EXISTS predicates over a probabilistic database. In QDB\/MUD. 73--86.  Ting-You Wang Christopher R\u00e9 and Dan Suciu. 2008. Implementing NOT EXISTS predicates over a probabilistic database. In QDB\/MUD. 73--86."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00297-X"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2877203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2877203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:10Z","timestamp":1750221550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2877203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,24]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,4,7]]}},"alternative-id":["10.1145\/2877203"],"URL":"https:\/\/doi.org\/10.1145\/2877203","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,24]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}