Skip to content Search
Search our website:

Ontology-Based Data Access and Non-Uniform Constraint Satisfaction

  • Speaker: Professor Frank Wolter, Department of Computer Science, University of Liverpool.
  • Date: Wednesday, 19 March 2014 from 16:30 to 17:40
  • Location: Room 745, Birkbeck Main Building

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this talk, we discuss several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment.

We then establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. These connections are exploited to obtain results regarding first-order and datalog-rewritability of ontology-mediated queries and P/NP dichotomies for ontology-mediated queries.