Distribution Constraints: The Chase for Distributed Data

Autor:	Geck, Gaetano, Neven, Frank, Schwentick, Thomas
Jazyk:	angličtina
Rok vydání:	2020
Předmět:	FOS: Computer and information sciences distributed evaluation Computer Science - Databases chase Databases (cs.DB) tuple-generating dependencies conjunctive queries Computer Science::Databases
Popis:	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. LIPIcs, Vol. 155, 23rd International Conference on Database Theory (ICDT 2020), pages 13:1-13:19
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0291184f43d6edcd16b3537506d5f629 http://arxiv.org/abs/2003.00965 Zobrazit plný text záznamu