The Limits of Querying Ontologies

We study query answering in Description Logics (DLs). In particular, we consider conjunctive queries, unions of conjunctive queries, and their extensions with safe negation or inequality, which correspond to well-known classes of relational algebra queries. We provide a set of decidability, undecidability and complexity results for answering queries of the above languages over various classes of Description Logics knowledge bases. In general, such results show that extending standard reasoning tasks in DLs to answering relational queries is unfeasible in many DLs, even in inexpressive ones. In particular: (i) answering even simple conjunctive queries is undecidable in some very expressive DLs in which standard DL reasoning is decidable; (ii) in DLs where answering (unions of) conjunctive queries is decidable, adding the possibility of expressing safe negation or inequality leads in general to undecidability of query answering, even in DLs of very limited expressiveness. We also highlight the negative consequences of these results for the integration of ontologies and rules. We believe that these results have important implications for ontology-based information access, in particular for the design of query languages for ontologies.