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 |
WEB OF SCIENCETM
Citations
2
checked on Apr 24, 2024
Page view(s)
120
checked on Sep 7, 2022
Download(s)
96
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.