Michael Zakharyaschev Made a Report "Ontology-based data access: succinctness and complexity"

December 17, Michael Zakharyaschev, professor of computer science at Department of Computer Science and Information Systems, University of London, Birkbeck gave a presentation at a seminar of International Laboratory for Intelligent Systems and Structural Analysis.

Ontology-based data access and management (OBDA) is a popular paradigm of organising access to various types of data sources that has been developed since the mid 2000s. In a nutshell, OBDA separates the user from the data sources (relational databases, triple stores, etc.) by means of an ontology, which provides the user with a convenient query vocabulary, hides the structure of the data sources, enriches incomplete data with background knowledge, and supports queries to multiple and possibly heterogeneous data sources. A key concept of OBDA is first-order rewritability, which reduces the problem of answering ontology-mediated queries (OMQs) to standard database query evaluation. 

The aim of this talk is to give an introduction to OBDA via query rewriting, discuss its computational costs, and real-world applications. In particular, we consider two fundamental computational problems in OBDA with the W3C standard ontology language OWL 2 QL - the succinctness problem for first-order rewritings, and the complexity problem for OMQ evaluation - and show how these problems are related to classical circuit complexity and database query evaluation