Expressiveness of guarded existential rule languages
Expressiveness of guarded existential rule languages
复制标题
DOI：
10.1145/2594538.2594556
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
G. Gottlob;S. Rudolph;M. Šimkus
中科院分区：
文献类型：
--
作者：
G. Gottlob;S. Rudolph;M. Šimkus
所谓的存在规则最近引起了人们的关注，主要是因为它们对于本体查询回答具有足够的表达能力。已经引入了此类规则的几个可判定片段，采用诸如各种形式的防护之类的限制来确保可判定性。这个领域中一些更知名的语言是存在规则的（弱）守卫和（弱）边界守卫片段。在本文中，我们探讨了它们的相对和绝对表达力。特别是，我们提供了一个新的证据，证明通过边界保护和保护规则表达的查询可以转换为简单的数据记录查询。由于逆向翻译是不可能的，我们将前沿守卫和守卫规则分别推广为近前沿守卫和近守卫规则，这正是 Datalog 的表达能力。我们进一步证明，弱边境守卫规则可以转化为弱守卫规则，因此，弱边境守卫和弱守卫规则具有完全相同的表达能力。此类规则无法转换为 Datalog，因为它们的查询回答问题在数据复杂性上是 ExpTime-complete。我们通过证明在有序数据库上和输入否定可用的情况下，弱保护规则捕获在指数时间内可判定的所有查询来强化这一结果。然后，我们证明，用分层否定扩展的弱保护规则具有足够的表达能力，可以捕获指数时间内可判定的所有数据库查询，而无需对输入数据库进行任何假设。最后，我们注意到，本文的翻译通常在大小上呈指数级增长，但会导致使用所考虑的语言进行查询回答的最坏情况最优算法。
The so-called existential rules have recently gained attention, mainly due to their adequate expressiveness for ontological query answering. Several decidable fragments of such rules have been introduced, employing restriction such as various forms of guardedness to ensure decidability. Some of the more well-known languages in this arena are (weakly) guarded and (weakly) frontier-guarded fragments of existential rules. In this paper, we explore their relative and absolute expressiveness. In particular, we provide a new proof that queries expressed via frontier-guarded and guarded rules can be translated into plain Datalog queries. Since the converse translations are impossible, we develop generalizations of frontier-guarded and guarded rules to nearly frontier-guarded and nearly guarded rules, respectively, which have exactly the expressive power of Datalog. We further show that weakly frontier-guarded rules can be translated into weakly guarded rules, and thus, weakly frontier-guarded and weakly guarded rules have exactly the same expressive power. Such rules cannot be translated into Datalog since their query answering problem is ExpTime-complete in data complexity. We strengthen this result by showing that on ordered databases and with input negation available, weakly guarded rules capture all queries decidable in exponential time. We then show that weakly guarded rules extended with stratified negation are expressive enough to capture all database queries decidable in exponential time, without any assumptions about input databases. Finally, we note that the translations of this paper are, in general, exponential in size, but lead to worst-case optimal algorithms for query answering with considered languages.