{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T11:54:49Z","timestamp":1782388489349,"version":"3.54.5"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,2,21]],"date-time":"2017-02-21T00:00:00Z","timestamp":1487635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Research Foundation Flanders","doi-asserted-by":"crossref","award":["G037713"],"award-info":[{"award-number":["G037713"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2017,2,21]]},"abstract":"<jats:p>Evaluating queries over massive amounts of data is a major challenge in the big data era. Modern massively parallel systems, such as, Spark, organize query answering as a sequence of rounds each consisting of a distinct communication phase followed by a computation phase. The communication phase redistributes data over the available servers, while in the subsequent computation phase each server performs the actual computation on its local data. There is a growing interest in single-round algorithms for evaluating multiway joins where data is first reshuffled over the servers and then evaluated in a parallel but communication-free way. As the amount of communication induced by a reshuffling of the data is a dominating cost in such systems, we introduce a framework for reasoning about data partitioning to detect when we can avoid the data reshuffling step. Specifically, we formalize the decision problems parallel-correctness and transfer of parallel-correctness, provide semantical characterizations, and obtain tight complexity bounds.<\/jats:p>","DOI":"10.1145\/3041063","type":"journal-article","created":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T13:06:52Z","timestamp":1488200812000},"page":"93-100","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Reasoning on data partitioning for single-round multi-join evaluation in massively parallel systems"],"prefix":"10.1145","volume":"60","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gaetano","family":"Geck","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Hasselt, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_2_1","volume-title":"Parallel-correctness and transferability for conjunctive queries, submitted for journal publication","author":"Ameloot T.J.","year":"2015","unstructured":"Ameloot , T.J. , Geck , G. , Ketsman , B. , Neven , F. , Schwentick , T. Parallel-correctness and transferability for conjunctive queries, submitted for journal publication ( 2015 ). Ameloot, T.J., Geck, G., Ketsman, B., Neven, F., Schwentick, T. Parallel-correctness and transferability for conjunctive queries, submitted for journal publication (2015)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"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\/1807167.1807273"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90048-8"},{"key":"e_1_2_1_10_1","volume-title":"International Conference on Database Theory","author":"Geck G.","year":"2016","unstructured":"Geck , G. , Ketsman , B. , Neven , F. , Schwentick , T. Parallel-correctness and containment for conjunctive queries with union and negation . In International Conference on Database Theory ( 2016 ), 9: 1--9:17. Geck, G., Ketsman, B., Neven, F., Schwentick, T. Parallel-correctness and containment for conjunctive queries with union and negation. In International Conference on Database Theory (2016), 9:1--9:17."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594530"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920886"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.03.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989444"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376726"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564757"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536232"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687609"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00219-4"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen T.L.","year":"2014","unstructured":"Veldhuizen , T.L. Triejoin : A simple, worst-case optimal join algorithm . In Proceedings of the 17th International Conference on Database Theory (ICDT) ( 2014 ), 96--106. Veldhuizen, T.L. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT) (2014), 96--106."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465288"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3041063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3041063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:51Z","timestamp":1750220631000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3041063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,21]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,2,21]]}},"alternative-id":["10.1145\/3041063"],"URL":"https:\/\/doi.org\/10.1145\/3041063","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,21]]},"assertion":[{"value":"2017-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}