Abstract

We study the problem of finite ontology mediated query answering (FOMQA), thevariant of OMQA where the represented world is assumed to be finite, and thusonly finite models of the ontology are considered. We adopt the most typicalsetting with unions of conjunctive queries and ontologies expressed indescription logics (DLs). The study of FOMQA is relevant in settings that arenot finitely controllable. This is the case not only for DLs without the finitemodel property, but also for those allowing transitive role declarations. Whentransitive roles are allowed, evaluating queries is challenging: FOMQA isundecidable for SHOIF and only known to be decidable for the Horn fragment ofALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI,SOF, and SIF. Our approach is to characterise models relevant for decidingfinite query entailment. Relying on a certain regularity of these models, wedevelop automata-based decision procedures with optimal complexity bounds.

 

Introduction (beta)

None

 

Conclusion (beta)

None