| Autor: |
Geck, Gaetano, Ketsman, Bas, Neven, Frank, Schwentick, Thomas |
| Rok vydání: |
2015 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
