www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/21060
Link to publication: http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=5778
DOI: 10.4230/LIPIcs.ICDT.2016.9
ISBN: 978-3-95977-002-6
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A580.86 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.