{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:32Z","timestamp":1750306352881,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T00:00:00Z","timestamp":1464825600000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2016,6,2]]},"abstract":"<jats:p>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 is 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 parallel-correctness, for the evaluation of queries w.r.t. a distribution policy. We provide a semantical characterization for when conjunctive queries (and extensions thereof) are parallel-correct and give matching complexity bounds for the associated decision problem.<\/jats:p>\n          <jats:p>Motivated by scenarios for workload optimization, we further consider the problem of parallel-correctness transfer from a query Q to a query Q0, that is, whether Q0 is parallelcorrect for all distribution policies for which Q is parallelcorrect. In this case, Q0 can always be evaluated after Q without repartitioning the data. We provide a semantical characterization for parallel-correctness transfer and provide matching complexity bounds for the associated decision problem for conjunctive queries (and extensions). Finally, we investigate restrictions of queries and families of distribution policies with better complexities, including, for instance, the Hypercube distributions.<\/jats:p>","DOI":"10.1145\/2949741.2949750","type":"journal-article","created":{"date-parts":[[2016,6,3]],"date-time":"2016-06-03T12:14:26Z","timestamp":1464956066000},"page":"33-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Data partitioning for single-round multi-join evaluation in massively parallel systems"],"prefix":"10.1145","volume":"45","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University &amp; transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaetano","family":"Geck","sequence":"additional","affiliation":[{"name":"TU Dortmund University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Hasselt University &amp; transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University &amp; transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745759"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745759"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90048-8"},{"key":"e_1_2_1_8_1","first-page":"1","volume-title":"International Conference on Database Theory","author":"Geck G.","year":"2016","unstructured":"G. Geck , B. Ketsman , F. Neven , and T. Schwentick . Parallel-correctness and containment for conjunctive queries with union and negation . In International Conference on Database Theory , pages 9: 1 -- 9 :17, 2016 . G. Geck, B. Ketsman, F. Neven, and T. Schwentick. Parallel-correctness and containment for conjunctive queries with union and negation. In International Conference on Database Theory, pages 9:1--9:17, 2016."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594530"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.03.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989444"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_14_1","volume-title":"Principles of Distributed Database Systems","author":"\u00d6zsu M. T.","year":"2011","unstructured":"M. T. \u00d6zsu and P. Valduriez . Principles of Distributed Database Systems , Third Edition. Springer , 2011 . M. T. \u00d6zsu and P. Valduriez. Principles of Distributed Database Systems, Third Edition. Springer, 2011."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564757"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00219-4"},{"key":"e_1_2_1_18_1","first-page":"96","volume-title":"Proc. 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . Triejoin : A simple, worst-case optimal join algorithm . In Proc. 17th International Conference on Database Theory (ICDT) , pages 96 -- 106 , 2014 . T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International Conference on Database Theory (ICDT), pages 96--106, 2014."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465288"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2949741.2949750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2949741.2949750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:00Z","timestamp":1750222560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2949741.2949750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,2]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,2]]}},"alternative-id":["10.1145\/2949741.2949750"],"URL":"https:\/\/doi.org\/10.1145\/2949741.2949750","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2016,6,2]]},"assertion":[{"value":"2016-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}