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
Source: 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.
Keywords: Conjunctive queries; parallel-correctness; containment
Document URI: http://hdl.handle.net/1942/29779
ISSN: 1529-3785
e-ISSN: 1557-945X
DOI: 10.1145/3329120
ISI #: 000475734700006
Rights: 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
Category: A1
Type: Journal Contribution
Validations: ecoom 2020
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
a18-geck (1).pdf
  Restricted Access
Published version363.02 kBAdobe PDFView/Open    Request a copy
Show full item record

Google ScholarTM

Check

Altmetric


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