  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 paper extends the study of the complexity of parallel-correctness and its
constituents, parallel-soundness and parallel-completeness, to unions of
conjunctive queries with and without negation. As a by-product it is shown that
the containment problem for conjunctive queries with negation is
coNEXPTIME-complete.
