Departmental Seminar: Non-Uniform Data Complexity in Ontology-Based Data Access with Description Logics

In recent years, the use of ontologies to access instance data has become increasingly popular. The general idea is that an ontology (a logical theory) gives a semantics to the predicates used in the database, thus allowing more complete answers to queries, enriching the vocabulary available for querying, and facilitating translation when the data vocabulary and the query vocabulary are different.

In this presentation, I will focus on ontologies formulated in description logics (DLs) and advocate a novel approach to studying the data complexity of query answering w.r.t. DL ontologies. This approach is non-uniform in the sense that individual ontologies are considered instead of all ontologies that can be formulated in a given DL. It allows us to ask rather fine-grained questions about the data complexity of DLs, such as: given a DL L, how can one characterize the ontologies for which query answering is in PTime or FO-rewritable? Is there a dichotomy between being in PTime and being coNP-hard? We provide several answers to such questions, some of which are based on a novel  connection between query answering w.r.t. DL ontologies and constraint satisfaction problems (CSPs) that allows us to transfer various results from CSPs to DLs. We also identify a class of ontologies within the expressive DL ALCFI that enjoy PTime data complexity; the new class strictly extends the Horn fragment of ALCFI, which was was the largest known tractable fragment of ALCFI so far.

The talk is based on joint work with Frank Wolter.