Distribution Policies for Datalog
Autor: | Bas Ketsman, Paraschos Koutris, Aws Albarghouthi |
---|---|
Přispěvatelé: | Informatics and Applied Informatics, Amsterdamer, Yael, Kimelfeld, Benny, Software Languages Lab |
Rok vydání: | 2019 |
Předmět: |
Evaluation strategy
000 Computer science knowledge general works Speedup Theoretical computer science Computer science business.industry Computation Data management Joins Datalog queries Predicate (grammar) Theoretical Computer Science Datalog Computational Theory and Mathematics Distributed evaluation Distribution policies Computer Science Theory of computation distribution policies business computer Software computer.programming_language |
Zdroj: | Theory of Computing Systems. 64:965-998 |
ISSN: | 1433-0490 1432-4350 |
Popis: | Modern data management systems extensively use parallelism to speed up query processing over massive volumes of data. This trend has inspired a rich line of research on how to formally reason about the parallel complexity of join computation. In this paper, we go beyond joins and study the parallel evaluation of recursive queries. We introduce a novel framework to reason about multi-round evaluation of Datalog programs, which combines implicit predicate restriction with distribution policies to allow expressing a combination of data-parallel and query-parallel evaluation strategies. Using our framework, we reason about key properties of distributed Datalog evaluation, including parallel-correctness of the evaluation strategy, disjointness of the computation effort, and bounds on the number of communication rounds. |
Databáze: | OpenAIRE |
Externí odkaz: |