Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity
Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and Complexity
复制标题
DOI：
10.1145/3447508
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
G. Gottlob;André Hernich;C. Kupke;Thomas Lukasiewicz
中科院分区：
文献类型：
--
作者：
G. Gottlob;André Hernich;C. Kupke;Thomas Lukasiewicz
这项工作根据经典稳定模型语义，研究了具有非单调否定的受保护存在规则下数据库查询应答的可判定性和复杂性。在这种情况下，存在量化通过 Skolem 函数进行解释，并采用唯一名称假设。作为第一个结果，我们通过转换为具有树模型属性的受保护二阶公式的可满足性问题，展示了基于此类规则回答一阶查询的可判定性。为了获得合取查询并集的精确复杂度结果，我们将多项式时间内的原始问题转化为更容易分析的中间问题：使用分层否定对受保护的析取存在规则进行查询回答。我们获得了一般设置和各种限制设置的精确界限。我们还考虑了原始形式主义的扩展，包括否定约束、键以及查询中否定原子的可能性。最后，我们展示了如何使用上述结果来提供可判定性和复杂性结果，以实现稳定模型语义自然适应描述逻辑（例如 ELHI 和 DL-Lite 系列）。
This work investigates the decidability and complexity of database query answering under guarded existential rules with nonmonotonic negation according to the classical stable model semantics. In this setting, existential quantification is interpreted via Skolem functions, and the unique name assumption is adopted. As a first result, we show the decidability of answering first-order queries based on such rules by a translation into the satisfiability problem for guarded second-order formulas having the tree-model property. To obtain precise complexity results for unions of conjunctive queries, we transform the original problem in polynomial time into an intermediate problem that is easier to analyze: query answering for guarded disjunctive existential rules with stratified negation. We obtain precise bounds for the general setting and for various restricted settings. We also consider extensions of the original formalism with negative constraints, keys, and the possibility of negated atoms in queries. Finally, we show how the above results can be used to provide decidability and complexity results for a natural adaptation of the stable model semantics to description logics such as ELHI and the DL-Lite family.