Parallel-correctness and transferability for conjunctive queries under bag semantics

Abstract

Due to the increasing popularity of cloud computing and big data, there is a growing need for data processing in distributed and parallel settings. Of particular interest are the evaluations of queries in a single-round of communication where data is distributed over different servers according to some distribution policy, after which each server evaluates the query over the locally available data. Based on this setting, a correctness condition called parallel-correctness has been studied as well as transferability of parallel-correctness while considering unions of conjunctive queries under set semantics. In this thesis, we extend this study toward bag semantics, as bag semantics are often used in practice and their usage is inevitable for certain aggregation functions. We provide characterizations for both parallel-correctness and transferability for conjunctive queries with inequalities under bag semantics and use these characterizations to study the complexity of these problems. The existing distributed evaluation model is however quite restrictive on possible distribution policies for certain conjunctive queries under bag semantics. We therefore propose a slightly modified model based on ordered networks.