License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.14
URN: urn:nbn:de:0030-drops-103165
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10316/
Neven, Frank ;
Schwentick, Thomas ;
Spinrath, Christopher ;
Vandevoort, Brecht
Parallel-Correctness and Parallel-Boundedness for Datalog Programs
Abstract
Recently, Ketsman et al. started the investigation of the parallel evaluation of recursive queries in the Massively Parallel Communication (MPC) model. Among other things, it was shown that parallel-correctness and parallel-boundedness for general Datalog programs is undecidable, by a reduction from the undecidable containment problem for Datalog. Furthermore, economic policies were introduced as a means to specify data distribution in a recursive setting. In this paper, we extend the latter framework to account for more general distributed evaluation strategies in terms of communication policies. We then show that the undecidability of parallel-correctness runs deeper: it already holds for fragments of Datalog, e.g., monadic and frontier-guarded Datalog, with a decidable containment problem, under relatively simple evaluation strategies. These simple evaluation strategies are defined w.r.t. data-moving distribution constraints. We then investigate restrictions of economic policies that yield decidability. In particular, we show that parallel-correctness is 2EXPTIME-complete for monadic and frontier-guarded Datalog under hash-based economic policies. Next, we consider restrictions of data-moving constraints and show that parallel-correctness and parallel-boundedness are 2EXPTIME-complete for frontier-guarded Datalog. Interestingly, distributed evaluation no longer preserves the usual containment relationships between fragments of Datalog. Indeed, not every monadic Datalog program is equivalent to a frontier-guarded one in the distributed setting. We illustrate the latter by considering two alternative settings where in one of these parallel-correctness is decidable for frontier-guarded Datalog but undecidable for monadic Datalog.
BibTeX - Entry
@InProceedings{neven_et_al:LIPIcs:2019:10316,
author = {Frank Neven and Thomas Schwentick and Christopher Spinrath and Brecht Vandevoort},
title = {{Parallel-Correctness and Parallel-Boundedness for Datalog Programs}},
booktitle = {22nd International Conference on Database Theory (ICDT 2019)},
pages = {14:1--14:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-101-6},
ISSN = {1868-8969},
year = {2019},
volume = {127},
editor = {Pablo Barcelo and Marco Calautti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10316},
doi = {10.4230/LIPIcs.ICDT.2019.14},
annote = {Keywords: Datalog, distributed databases, distributed evaluation, decision problems, complexity}
}
|
Keywords: |
|
Datalog, distributed databases, distributed evaluation, decision problems, complexity |
|
Collection: |
|
22nd International Conference on Database Theory (ICDT 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
19.03.2019 |
