Conjunctive Query Answering for Expressive Description Logics

Intelligent systems are often realised with logic-based data and knowledge representation formalisms. This has various advantages in comparison to classical databases. For example, it is possible to represent inhomogeneously structured information with a flexible schema. Moreover, such systems have the benefit that logically implied conclusions in the represented knowledge can automatically be derived by reasoning algorithms. A very important reasoning service is answering conjunctive queries, which constitutes also the basis of the SPARQL query language that is widely used in the area of the Semantic Web. The knowledge representation formalism is often based on Description Logics (e.g., OWL), which is a family of decidable fragments of First Order Logics. So far, there exist, however, no practically usable techniques for answering conjunctive queries with expressive Description Logics. Nevertheless, such logics are often used in practice since they provide more modelling constructors and, therefore, they allow for representing knowledge and data in more detail.

With this project, we propose a novel technique for conjunctive query answering with very expressive Description Logics. The approach is based on a deep integration into reasoning procedures, where the conjunctive queries are transformed (absorbed) into rule-based axioms, which are directly handled by specialised reasoning algorithms. In contrast, existing approaches use reasoning systems as black-boxes and reduce query answering to standard reasoning services. The direct and deep integration also allows for more sophisticated optimisations and, therefore, promises a much better performance for answering conjunctive queries. Furthermore, logically implied but not explicitly stated individuals in the represented knowledge can be considered efficiently, i.e., computing all logically implied answers becomes feasible in practice.

For absorbing the queries, we plan to use so-called nominal schemas, for which we developed efficient reasoning algorithms in our recent preliminary work. First, we plan to extend absorption using nominal schemas to conjunctive queries in such a way that the resulting rule-based expressions can be handled by suitably extended reasoning procedures. Second, we plan to analyse theoretically as well as practically for which language fragments the approach can be applied. Third, we plan to develop and realise specific optimisations such that the technique can benefit from the deeper integration into the reasoning procedure and scales well to larger amounts of data. Last but not least, we plan to empirically evaluate our novel conjunctive query answering approach with existing techniques.

The proposed project significantly improves the practical usability of more expressive Description Logics, which allows for a more detailed modelling and representation of data and knowledge in practical information systems.

Project period: March 2018 to February 2021

Project Members

  • Andreas Steigmiller (principal investigator)