PAC: Computing Join Queries with Semi-Covers
ACM Transactions on Database Systems · 31.03.2027 · 52 (1) · 1-36
DOI: 10.1145/3820043 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 14.11.2026. Verfasst von Heba Aamer und 1 weiteren Autor:innen. Die Arbeit nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fonds Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
An increased and growing interest in large-scale data processing has triggered a demand for specialized algorithms that thrive in massively parallel shared-nothing systems. To answer the question of how to efficiently compute join queries in this setting, a rich line of research has emerged specifically for the Massively Parallel Communication (MPC) model. In the MPC model, algorithms are executed in rounds, with each round consisting of a synchronized communication phase and a separate local computation phase. The main cost measure is the load of the algorithm, defined as the maximum number of messages received by any server in any round. We study worst-case optimal algorithms for the join query evaluation problem in the constant-round MPC model. In the single-round variant of the MPC model, the worst-case optimal load for this problem is well understood and algorithms exist that guarantee this load for any join query. In the constant-round variant of the MPC model, queries can often be computed with a lower load compared to the single-round variant, but the worst-case optimal load is only known for specific classes of queries, including the graph-like join queries and the acyclic join queries. Each of these classes has its own associated algorithms to achieve the worst-case optimal load, and these algorithms rely on very different techniques that are specific to the class. In this article, we propose a new, unified constant-round MPC algorithm for computing join queries. This algorithm is correct for every join query and preserves the worst-case optimal load for many queries, particularly all join queries that are acyclic or graph-like. Additionaly, the algorithm is shown to be worst-case optimal for a new class of cyclic queries.
Förderung
- Fonds Wetenschappelijk Onderzoek
Zitieren
APA
Aamer, H., & Ketsman, B. (2027). PAC: Computing Join Queries with Semi-Covers. ACM Transactions on Database Systems, 52(1), 1-36. https://doi.org/10.1145/3820043
Vancouver
Aamer H, Ketsman B. PAC: Computing Join Queries with Semi-Covers. ACM Transactions on Database Systems. 2027;52(1):1-36. doi:10.1145/3820043
BibTeX
@article{Aamer2027,
author = {Aamer, Heba and Ketsman, Bas},
title = {PAC: Computing Join Queries with Semi-Covers},
journal = {ACM Transactions on Database Systems},
year = {2027},
volume = {52},
number = {1},
pages = {1--36},
doi = {10.1145/3820043}
}
EUVIMED