In recent years, the use of ontologies to access instance data has become increasingly popular. The general idea is that an ontology provides a vocabulary or conceptual model for the application domain, which can then be used as an interface for querying instance data and to derive additional facts.
In this presentation, I will first introduce ontology-based data access (OBDA). I will focus on ontologies given in description logics or, equivalently, the web ontology language OWL. I will then establish a very close link between OBDA and constraint satisfaction problems with finite templates (CSP). Rather surprisingly, for the basic description logic ALC (=modal logic) OBDA and CSP turn out to be essentially equivalent. This result has a large number of consequences for ALC and OBDA in general.
I will focus on the following non-uniform complexity problem: what is the complexity of query answering for a fixed ontology? I will present general conditions under which this problem is in PTime and, respectively, coNP-hard. Using the CSP connection is is shown that for ALC there is a P/coNP dichotomy for conjunctive query answering if, and only if, the famous, and still open, Feder/Vardi dichotomy conjecture for CSP holds.

The talk is based on joint work with Carsten Lutz.