Chase Termination for Guarded Existential Rules
Chase Termination for Guarded Existential Rules
复制标题
保护存在规则的 Chase 终止
DOI：
10.1145/2745754.2745773
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Andreas Pieris
中科院分区：
文献类型：
--
作者：
M. Calautti;G. Gottlob;Andreas Pieris
Chase过程被认为是数据库理论中最基本的算法工具之一。它已成功地应用于不同的数据库问题，如数据交换，查询应答和约束下的遏制，仅举几例。关于chase过程的中心问题之一是所有实例终止，也就是说，给定一组元组生成依赖关系（tuple-generating dependencies，TGD）（a.k.a.存在规则），决定对于每个输入数据库，在该集合下的追逐是否终止。众所周知，这个问题是不可判定的，无论我们考虑哪种版本的追逐。出现的关键问题是，是否现有的限制类的TGD，提出在不同的情况下，如本体查询回答，使上述问题可判定。在这项工作中，我们把我们的注意力集中在不经意的和半不经意的版本的追逐过程中，我们给出了一个积极的答案类的TGD是基于守护的概念。据我们所知，这是第一个工作，建立积极的结果（半）遗忘追逐终止问题。特别是，我们首先集中在类的线性TGD，我们的语法特征，通过丰富的和弱的无环性，它的片段，保证终止的遗忘和半遗忘的追逐，分别。这些句法特征，除了本身很有趣之外，还让我们能够确定问题的复杂性，一般来说，这是PSPACE完全的，如果我们专注于有界元的谓词，对于遗忘和半遗忘的追逐，则是NL完全的。然后，我们继续更一般的类别的保护和弱保护的TGD。虽然我们不提供其相关片段的句法特征，线性TGD，我们表明，所考虑的问题仍然是可判定的。事实上，我们表明，它是2 EXPTIME-完全的一般情况下，和EXPTIME-完全的，如果我们专注于有界arity的谓词，无论是不经意的和半不经意的追逐。最后，我们调查的表达能力，从我们的分析获得的查询语言，我们表明，他们是同样的表达与标准的数据库查询语言。然而，我们有强烈的迹象表明，它们更加简洁。
The chase procedure is considered as one of the most fundamental algorithmic tools in database theory. It has been successfully applied to different database problems such as data exchange, and query answering and containment under constraints, to name a few. One of the central problems regarding the chase procedure is all-instance termination, that is, given a set of tuple-generating dependencies (TGDs) (a.k.a. existential rules), decide whether the chase under that set terminates, for every input database. It is well-known that this problem is undecidable, no matter which version of the chase we consider. The crucial question that comes up is whether existing restricted classes of TGDs, proposed in different contexts such as ontological query answering, make the above problem decidable. In this work, we focus our attention on the oblivious and the semi-oblivious versions of the chase procedure, and we give a positive answer for classes of TGDs that are based on the notion of guardedness. To the best of our knowledge, this is the first work that establishes positive results about the (semi-)oblivious chase termination problem. In particular, we first concentrate on the class of linear TGDs, and we syntactically characterize, via rich- and weak-acyclicity, its fragments that guarantee the termination of the oblivious and the semi-oblivious chase, respectively. Those syntactic characterizations, apart from being interesting in their own right, allow us to pinpoint the complexity of the problem, which is PSPACE-complete in general, and NL-complete if we focus on predicates of bounded arity, for both the oblivious and the semi-oblivious chase. We then proceed with the more general classes of guarded and weakly-guarded TGDs. Although we do not provide syntactic characterizations for its relevant fragments, as for linear TGDs, we show that the problem under consideration remains decidable. In fact, we show that it is 2EXPTIME-complete in general, and EXPTIME-complete if we focus on predicates of bounded arity, for both the oblivious and the semi-oblivious chase. Finally, we investigate the expressive power of the query languages obtained from our analysis, and we show that they are equally expressive with standard database query languages. Nevertheless, we have strong indications that they are more succinct.
非循环条件及其在描述逻辑查询应答中的应用
DOI：
--
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Cuenca Grau B
通讯作者：
Cuenca Grau B