From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying
This work addresses foundational issues in knowledge representation and query optimization for ontology-based systems, offering incremental theoretical advancements.
The paper tackles the problem of determining when ontology-mediated queries (OMQs) based on expressive description logics and conjunctive queries can be rewritten into OMQs based on instance queries, providing exact characterizations and tight complexity bounds for decidability.
We consider ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and (unions) of conjunctive queries, studying the rewritability into OMQs based on instance queries (IQs). Our results include exact characterizations of when such a rewriting is possible and tight complexity bounds for deciding rewritability. We also give a tight complexity bound for the related problem of deciding whether a given MMSNP sentence is equivalent to a CSP.