Abstract
We study the problem of finite ontology mediated query answering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA is relevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automata-based decision procedures with optimal complexity bounds.
Abstract (translated)
我们研究了有限本体介导的查询答案（FOMQA）的问题，这是OMQA的变体，其中假定代表的世界是有限的，因此只考虑本体的有限模型。我们采用最典型的设置，在描述逻辑（DL）中表达了联合查询和本体的联合。 FOMQA的研究与无限制可控的环境相关。不仅对于没有有限模型属性的DL，而且对于那些允许传递角色声明的DL也是如此。当允许传递角色时，评估查询具有挑战性：FOMQA对于SHOIF是不可判定的，并且只知道对于ALCIF的Horn片段是可判定的。我们展示了FOMQA对SOIF的三个适当片段的可判定性：SOI，SOF和SIF。我们的方法是表征与决定有限查询蕴涵相关的模型。依靠这些模型的某种规律性，我们开发了具有最佳复杂性界限的基于自动机的决策程序。
URL
https://arxiv.org/abs/1808.03130
