论文标题
具有全球和本地基数限制的逻辑中的满意度和查询回答
Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
论文作者
论文摘要
我们介绍和研究表达性描述逻辑（DL）ALCSCC ++，其中可以将上一篇论文中介绍的全局和局部基质限制混合在一起。一方面，我们证明这不会增加可满足性检查和其他标准推理问题的复杂性。另一方面，如果将反向角色添加到语言中，那么令人满意的问题就无法确定。此外，即使没有逆角色，此DL中的连接性查询却是不可决定的。我们证明，如果全球和局部约束不混杂并且全球约束受到适当限制，则可以恢复查询的可决定性。后一个结果基于本地隔离模型的构建，它在限制设置（即Abox一致性W.R.T. ALCSCC中受限制的基数约束，为此我们可以显示一个exptime上限。
We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints introduced in previous papers can be mixed. On the one hand, we prove that this does not increase the complexity of satisfiability checking and other standard inference problems. On the other hand, the satisfiability problem becomes undecidable if inverse roles are added to the languages. In addition, even without inverse roles, conjunctive query entailment in this DL turns out to be undecidable. We prove that decidability of querying can be regained if global and local constraints are not mixed and the global constraints are appropriately restricted. The latter result is based on a locally-acyclic model construction, and it reduces query entailment to ABox consistency in the restricted setting, i.e., to ABox consistency w.r.t. restricted cardinality constraints in ALCSCC, for which we can show an ExpTime upper bound.
