论文标题
用守卫的TGD来查询的更紧密的范围
Tighter Bounds for Query Answering with Guarded TGDs
论文作者
论文摘要
我们考虑开放世界查询答案问题的复杂性，我们希望通过一组最初的事实和一组受保护的TGD来确定不完整的数据集的某些答案。这个问题在文献中得到了很好的研究，是可决定的，但复杂性很高，即是2期完整的。此外，当Arity固定时，复杂性缩小了一个指数。 在本文中，我们在本文中表明，当分别考虑后卫原子和附加原子（称为侧面签名）的Arity时，如何获得更好的复杂性界限。我们的结果利用了Gottlob，Manna和Pieris引入的线性化守卫TGD的技术。具体而言，我们介绍了线性化过程的一种变体，利用了我们最近引入的限制版本的限制版本。我们的结果表明，如果我们只是绑定了侧面签名的敏锐度，则可以通过任意的守卫关系在exptime中解决开放世界的查询。如果我们固定侧面签名并绑定依赖项的宽度，那么复杂性就会降至NP。
We consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an initial set of facts and a set of guarded TGDs. This problem has been well-studied in the literature and is decidable but with a high complexity, namely, it is 2EXPTIME complete. Further, the complexity shrinks by one exponential when the arity is fixed. We show in this paper how we can obtain better complexity bounds when considering separately the arity of the guard atom and that of the additional atoms, called the side signature. Our results make use of the technique of linearizing guarded TGDs, introduced in Gottlob, Manna, and Pieris. Specifically, we present a variant of the linearization process, making use of a restricted version of the chase that we recently introduced. Our results imply that open-world query answering with guarded TGDs can be solved in EXPTIME with arbitrary-arity guard relations if we simply bound the arity of the side signature; and that the complexity drops to NP if we fix the side signature and bound the width of the dependencies.
