{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T06:38:30Z","timestamp":1756190310371,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T00:00:00Z","timestamp":1504483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Foundation-Flanders"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            A dominant cost for query evaluation in modern massively distributed systems is the number of communication rounds. For this reason, there is a growing interest in single-round multiway join algorithms where data are first reshuffled over many servers and then evaluated in a parallel but communication-free way. The reshuffling itself is specified as a distribution policy. We introduce a correctness condition, called\n            <jats:italic>parallel-correctness<\/jats:italic>\n            , for the evaluation of queries w.r.t. a distribution policy. We study the complexity of parallel-correctness for conjunctive queries as well as transferability of parallel-correctness between queries. We also investigate the complexity of transferability for certain families of distribution policies, including the Hypercube distribution policies.\n          <\/jats:p>","DOI":"10.1145\/3106412","type":"journal-article","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T12:23:34Z","timestamp":1504614214000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Parallel-Correctness and Transferability for Conjunctive Queries"],"prefix":"10.1145","volume":"64","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg, Hasselt, Belgium"}]},{"given":"Gaetano","family":"Geck","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Otto-Hahn-Stra\u00dfe, Dortmund"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg, Hasselt, Belgium"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg, Hasselt, Belgium"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Otto-Hahn-Stra\u00dfe, Dortmund"}]}],"member":"320","published-online":{"date-parts":[[2017,9,4]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274605"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745759"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2949741.2949750"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3041063"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594541"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_13_1","unstructured":"Michael Fellows. 1988. Planar Emulators and Planar Covers. (Unpublished manuscript).  Michael Fellows. 1988. Planar Emulators and Planar Covers. (Unpublished manuscript)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98724"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90048-8"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 19th International Conference on Database Theory (ICDT\u201916)","author":"Geck Gaetano","year":"2016","unstructured":"Gaetano Geck , Bas Ketsman , Frank Neven , and Thomas Schwentick . 2016 . Parallel-correctness and containment for conjunctive queries with union and negation . In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916) . 9:1--9:17. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ICDT.2016.9 10.4230\/LIPIcs.ICDT.2016.9 Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. 2016. Parallel-correctness and containment for conjunctive queries with union and negation. In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916). 9:1--9:17. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ICDT.2016.9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034788"},{"key":"e_1_2_1_20_1","first-page":"113","article-title":"Planar branched coverings of graphs","volume":"38","author":"Kitakubo Shigeru","year":"1991","unstructured":"Shigeru Kitakubo . 1991 . Planar branched coverings of graphs . Yokohama Math. J. 38 , 2 (1991), 113 -- 120 . Shigeru Kitakubo. 1991. Planar branched coverings of graphs. Yokohama Math. J. 38, 2 (1991), 113--120.","journal-title":"Yokohama Math. J."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 19th International Conference on Database Theory, (ICDT 2016","author":"Koutris Paraschos","year":"2016","unstructured":"Paraschos Koutris , Paul Beame , and Dan Suciu . 2016 . Worst-case optimal algorithms for parallel query processing . In Proceedings of the 19th International Conference on Database Theory, (ICDT 2016 , Bordeaux, France , March 15-18, 2016. 8:1--8:18. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ICDT.2016.8 10.4230\/LIPIcs.ICDT.2016.8 Paraschos Koutris, Paul Beame, and Dan Suciu. 2016. Worst-case optimal algorithms for parallel query processing. In Proceedings of the 19th International Conference on Database Theory, (ICDT 2016, Bordeaux, France, March 15-18, 2016. 8:1--8:18. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.ICDT.2016.8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_23_1","unstructured":"Spark 2014. Spark. (2014). http:\/\/spark.apache.org.  Spark 2014. Spark. (2014). http:\/\/spark.apache.org."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44669-9_49"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465288"},{"volume-title":"Algorithms for acyclic database schemes","author":"Yannakakis Mihalis","key":"e_1_2_1_27_1","unstructured":"Mihalis Yannakakis . 1981. Algorithms for acyclic database schemes . IEEE Press , 82--94. Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. IEEE Press, 82--94."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274588"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3106412","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3106412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:17Z","timestamp":1750217417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3106412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,4]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3106412"],"URL":"https:\/\/doi.org\/10.1145\/3106412","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,9,4]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}