Parallel-correctness and containment for conjunctive queries with union and negation

Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number18
Pages (from-to)1-24
Number of pages24
JournalACM Transactions on Computational Logic
Volume20
Issue number3
DOIs
Publication statusPublished - Jul 2019

Keywords

  • Conjunctive queries
  • Containment
  • Parallel-correctness

Fingerprint

Dive into the research topics of 'Parallel-correctness and containment for conjunctive queries with union and negation'. Together they form a unique fingerprint.

Cite this