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 | Size | Format | |
---|---|---|---|---|
a18-geck (1).pdf Restricted Access | Published version | 363.02 kB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.