Loading...
research article
Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
July 1, 2019
Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This article extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with negation. As a by-product, it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.
Use this identifier to reference this record
Type
research article
Web of Science ID
WOS:000475734700006
Authors
Publication date
2019-07-01
Publisher
Published in
Volume
20
Issue
3
Start page
18
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
August 1, 2019