2026-07-27T17:10:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15883 2024-03-06T10:56:26Z ddc:004 open_access

Parallel Acyclic Joins with Canonical Edge Covers Tao, Yufei Joins Conjunctive Queries MPC Algorithms Parallel Computing In PODS'21, Hu presented an algorithm in the massively parallel computation (MPC) model that processes any acyclic join with an asymptotically optimal load. In this paper, we present an alternative analysis of her algorithm. The novelty of our analysis is in the revelation of a new mathematical structure - which we name canonical edge cover - for acyclic hypergraphs. We prove non-trivial properties for canonical edge covers that offer us a graph-theoretic perspective about why Hu’s algorithm works. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yufei Tao 2022 Is Part Of LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2022.9 urn:nbn:de:0030-drops-158838 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode