Ontology-mediated query answering and query rewriting

24^th March 2015, 13:00 Ashton Lecture Theater
Dr Meghyn Bienvenu
Laboratoire de Recherche en Informatique (LRI)
CNRS & Universite Paris-Sud
France

Abstract

Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. Adding an ontology has several advantages (e.g. simplifying query formulation, integrating data from different sources, providing more complete answers to queries), but it also makes the query answering task more difficult. Query rewriting, which reduces OMQA to the evaluation of database queries, allows OMQA to be implemented on top of existing database systems, thereby benefitting from the maturity and performance of such systems.

In this talk, I will start by giving a short introduction to ontology-mediated query answering, focusing on ontologies formulated using description logics. Then I will consider two natural problems related to query rewriting (concerning the existence and succinctness of rewritings) and present some recent results that have been obtained by leveraging connections to constraint satisfaction problems and circuit complexity.