Reasoning in Very Expressive Description Logics with Varying Information Completeness

Abstract

Ontology-based data access (OBDA) is a prominent approach for enabling non-expert users to query diverse and incomplete data sources easily. OBDA abstracts the underlying data structure, presenting users with an ontology that provides a high-level conceptual view of the application domain and additionally stores background knowledge about it. Users pose queries using the vocabulary of the ontology, which are answered over integrated data supplemented with inferred facts. Answering these ontology-mediated queries (OMQs) is the central task in OBDA. Description logics (DLs) are key formalisms for expressing ontologies. Most DLs are fragments of first-order logica and as such they employ the open-world assumption (OWA). Intuitively, the OWA says that everything that is not forbidden is possible, which is generally appropriate for dealing with incomplete data. In contrast, when data is considered complete, it is more appropriate to employ the closed-world assumption (CWA) stating that what is not known to be true is assumed to be false. As complete and incomplete parts of data can interact, enriching DLs with some type of support for CWA is an active area of research. One particularly prominent approach adds to DLs the possibility of declaring certain predicates closed, i.e., that they should be interpreted under the CWA. This thesis explores computational and model-theoretic properties of expressive DLs with closed predicates. In particular, we provide new data complexity bounds for reasoning tasks in expressive DLs with closed predicates that support nominals, inverses, and number restrictions — a provably challenging combination. Notably, we show that deciding consistency of knowledge bases in DL ALCHOIQ remains NP-complete in data complexity with closed predicates, indicating that closed predicates do not increase computational complexity. We then turn to OMQs with closed predicates whose ontology component is expressed in one of our DLs of interest and we investigate their expressive power following two different directions. First, we compare the expressiveness of such OMQs to standard query languages like Datalog, presenting a polynomial-time rewriting of a large class of OMQs into Datalog with negation under stable model semantics, resulting in a co-NP-complete query answering problem. Second, we show that OMQs with ontologies in DL ALCHOI with closed predicates cannot express all co-NP- computable Boolean queries despite being co-NP-complete in data complexity and we propose an extension of the language that is powerful enough to do so. Additionally, we observe that closed predicates can affect knowledge base models, where interactions with numeric constraints may result in certain open predicates having bounded-size extensions. We present an algorithm to identify such predicates and provide a worst-case optimal bound for their extensions, supporting high-quality ontology construction and advancing decidability frontiers in data management. Finally, we explore a hybrid approach combining ontologies and non-monotonic rules, introducing Resilient Logic Programs (RLPs). RLPs can provide support for systems that need to react correctly in all situations, with reasoning reduced to checking hybrid knowledge base consistency. We show that RLPs are decidable and expressive, representing ∃∀∃-QBFs, disjunctive Datalog, and configuration problems under incomplete information. We identify a class of RLPs rewritable into disjunctive Datalog and present complexity results for RLPs with standard DL ontologies.