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/29779

Title: Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
Authors: Gaetano Geck
Ketsman, Bas
Neven, Frank
Thomas Schwentick
Issue Date: 2019
Citation: ACM Transactions on Computational Logic, 20(3), p. 1-24 (Art N° 18)
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 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/29779
DOI: 10.1145/3329120
ISI #: 000475734700006
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version363.02 kBAdobe PDF

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