Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21060
Title: | Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation | Authors: | GECK, Gaetano KETSMAN, Bas NEVEN, Frank Schwentick, Thomas |
Issue Date: | 2016 | Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | Source: | Martens, Wim; Zeume, Thomas (Ed.). LIPIcs–Leibniz International Proceedings in Informatics | Series/Report: | LIPIcs | Series/Report no.: | 48 | 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 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. | Keywords: | conjunctive queries; distributed evaluation | Document URI: | http://hdl.handle.net/1942/21060 | Link to publication/dataset: | http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=5778 | ISBN: | 978-3-95977-002-6 | DOI: | 10.4230/LIPIcs.ICDT.2016.9 | Rights: | © Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
6
checked on Sep 3, 2020
Page view(s)
68
checked on Sep 7, 2022
Download(s)
112
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.