Parallel-Correctness and Parallel-Boundedness for Datalog Programs
Parallel-Correctness and Parallel-Boundedness for Datalog Programs
复制标题
数据记录程序的并行正确性和并行有界性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Brecht Vandevoort
中科院分区：
文献类型：
--
作者：
F. Neven;T. Schwentick;Christopher Spinrath;Brecht Vandevoort
最近，Ketsman等人开始研究大规模并行通信（MPC）模型中递归查询的并行计算。通过对Datalog不可确定的包含问题的简化，证明了一般Datalog程序的并行正确性和并行有界性是不可确定的。此外，在递归设置中引入经济政策作为指定数据分布的手段。在本文中，我们扩展了后一种框架，以考虑通信策略方面更一般的分布式评估策略。然后，我们表明并行正确性的不可判定性更深：它已经适用于Datalog的片段，例如，在相对简单的求值策略下，具有可判定的包含问题的一元和边界保护Datalog。这些简单的求值策略是根据数据移动分布约束定义的。然后，我们研究了产生可决定性的经济政策的限制。特别是，我们证明了在基于哈希的经济政策下，一元和边界保护的Datalog的并行正确性是2EXPTIME-complete的。其次，我们考虑了数据移动约束的限制，并证明了边界保护数据的并行正确性和并行有界性是2EXPTIME-complete的。有趣的是，分布式计算不再保留Datalog片段之间通常的包含关系。实际上，并非每个一元Datalog程序都等同于分布式设置中的边界保护程序。我们通过考虑两种可选设置来说明后者，其中一种设置的并行正确性对于边界保护的Datalog是可确定的，而对于一元Datalog是不可确定的。
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.
带有保护否定的查询
DOI：
10.14778/2350229.2350250
发表时间：
2012
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
V. Bárány;B. ten Cate;M. Otto
通讯作者：
M. Otto