Dichotomies in Ontology-Mediated Querying with the Guarded Fragment

Andre Hernich, University of Liverpool. Part of the algebra, logic and algorithms seminar series.

In ontology-mediated querying we are given a database D (a finite set of facts), an ontology O (a finite set of sentences in some logic, typically first-order logic), and a query q (typically formulated in a 'light-weight' fragment of first-order logic), and the goal is to decide if q is entailed by D and O. Thus, ontology-mediated querying extends the traditional database querying setting by an ontology, which provides domain knowledge that will be taken into account in query evaluation. This problem has received a lot of attention recently in database theory as well as the knowledge representation and reasoning community. Most of the work in this area deals with identifying 'tractable' ontology languages - fragments of first-order logic or its extensions such that every ontology formulated in such a fragment admits tractable query answering. Oftentimes, however, applications require language features that are only available in more expressive and 'intractable' ontology languages, but that could still be added to an ontology in a way so that one can hope to avoid hardness. This motivates a more fine-grained study of query answering at the level of individual ontologies. Given an ontology, is it the case that query answering w.r.t. this ontology is tractable or is it intractable? This talk is about such a fine-grained complexity analysis for ontologies that can be expressed in the guarded fragment of first-order logic with counting, which captures a wide range of ontology languages that have been studied previously.

This is joint work with Carsten Lutz, Fabio Papacchini, and Frank Wolter, published at PODS 2017.

Andre Hernich, University of Liverpool