{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T06:27:11Z","timestamp":1756189631403,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"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. Comput. Logic"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This article extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with negation. As a by-product, it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.<\/jats:p>","DOI":"10.1145\/3329120","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8946-9440","authenticated-orcid":false,"given":"Gaetano","family":"Geck","sequence":"first","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4032-0709","authenticated-orcid":false,"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-1903","authenticated-orcid":false,"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1062-922X","authenticated-orcid":false,"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Software Foundation. 2010. Spark. Retrieved from: http:\/\/spark.apache.org.  Apache Software Foundation. 2010. Spark. Retrieved from: http:\/\/spark.apache.org."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1060"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274605"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT\u201910)","author":"Afrati F. N.","key":"e_1_2_1_4_1","unstructured":"F. N. Afrati and J. D. Ullman . 2010. Optimizing joins in a map-reduce environment . In Proceedings of the International Conference on Extending Database Technology (EDBT\u201910) . 99--110. F. N. Afrati and J. D. Ullman. 2010. Optimizing joins in a map-reduce environment. In Proceedings of the International Conference on Extending Database Technology (EDBT\u201910). 99--110."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106412"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594541"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"volume-title":"Proceedings of the Symposium on the Theory of Computing (STOC\u201977)","author":"Ashok","key":"e_1_2_1_10_1","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases . In Proceedings of the Symposium on the Theory of Computing (STOC\u201977) . 77--90. Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the Symposium on the Theory of Computing (STOC\u201977). 77--90."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_27"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90048-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201993)","author":"Alon","key":"e_1_2_1_15_1","unstructured":"Alon Y. Levy and Yehoshua Sagiv. 1993. Queries independent of updates . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201993) . 171--181. Alon Y. Levy and Yehoshua Sagiv. 1993. Queries independent of updates. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201993). 171--181."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.03.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055601"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00219-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_23"},{"volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD\u201913)","author":"Xin R.","key":"e_1_2_1_21_1","unstructured":"R. Xin , J. Rosen , M. Zaharia , M. Franklin , S. Shenker , and I. Stoica . 2013. Shark: SQL and rich analytics at scale . In Proceedings of the International Conference on Management of Data (SIGMOD\u201913) . R. Xin, J. Rosen, M. Zaharia, M. Franklin, S. Shenker, and I. Stoica. 2013. Shark: SQL and rich analytics at scale. In Proceedings of the International Conference on Management of Data (SIGMOD\u201913)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274588"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329120","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3329120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:41Z","timestamp":1750204481000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3329120"],"URL":"https:\/\/doi.org\/10.1145\/3329120","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}