文章基本信息

标题：Distribution Constraints: The Chase for Distributed Data
本地全文：下载
作者：Gaetano Geck ; Frank Neven ; Thomas Schwentick 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：155
页码：13:1-13:19
DOI：10.4230/LIPIcs.ICDT.2020.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper introduces a declarative framework to specify and reason about distributions of data over computing nodes in a distributed setting. More specifically, it proposes distribution constraints which are tuple and equality generating dependencies (tgds and egds) extended with node variables ranging over computing nodes. In particular, they can express co-partitioning constraints and constraints about range-based data distributions by using comparison atoms. The main technical contribution is the study of the implication problem of distribution constraints. While implication is undecidable in general, relevant fragments of so-called data-full constraints are exhibited for which the corresponding implication problems are complete for EXPTIME, PSPACE and NP. These results yield bounds on deciding parallel-correctness for conjunctive queries in the presence of distribution constraints.
关键词：tuple-generating dependencies; chase; conjunctive queries; distributed evaluation