Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
复制标题
通过加入非循环性和防护性来扩展可判定的存在规则
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S. Rudolph
中科院分区：
文献类型：
--
作者：
M. Krötzsch;S. Rudolph
存在规则，即在规则头中扩展了存在量词的数据日志，目前在各种名称下进行研究，如数据日志+/-、∀∃-规则和元组生成依赖关系。对这种形式主义的新兴趣是由大量最近发现的语言片段推动的，对于这些片段，查询答案是可以决定的。本文扩展和巩固了这一领域的两种主要方法-无循环和守卫-通过提供(1)保持复杂性的弱非循环和弱(边界)守卫规则的推广，以及(2)包含这两种规则的过剩(边界)守卫规则的一种新的形式主义。这建立在这样一种认识之上，即无循环可用于扩展任何存在规则语言，同时保持可判断性。除了可判断性之外，在所有情况下都建立了组合查询复杂性。
Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/-, ∀∃-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this field - acyclicity and guardedness - by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-) guarded rules, and (2) a novel formalism of glut-(frontier-) guarded rules that subsumes both. This builds on an insight that acyclicity can be used to extend any existential rule language while retaining decidability. Besides decidability, combined query complexities are established in all cases.