Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
复制标题
联合和否定的联合查询的并行正确性和包含性
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T. Schwentick
中科院分区：
文献类型：
--
作者：
Gaetano Geck;Bas Ketsman;F. Neven;T. Schwentick
单轮多路连接算法首先在许多服务器上重新洗牌数据，然后以并行和无通信的方式评估手头的查询。一个关键的问题是，一个给定的分配策略的洗牌是足够的计算一个给定的查询，也被称为并行正确性。本文扩展了并行正确性及其组成部分，并行可靠性和并行完整性的复杂性的研究，工会的合取查询与否定。作为一个副产品，它表明，包含问题与否定的合取查询是coNEXPTIME完全的。
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 article 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.