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.