We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.

  • A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

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