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

WEB OF SCIENCETM
Citations

2
checked on May 14, 2022

Page view(s)

112
checked on May 20, 2022

Download(s)

94
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


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