Video Library
Most viewed videos

New in collection

Conference «Contemporary Mathematics and its applications» dedicated to the results of research supported by the Russian Science Foundation grant 14-50-00005
November 19, 2018 15:10–15:30, Direction "Discrete mathematics and mathematical logic", Moscow, Steklov Mathematical Institute of RAS, Conference Hall (8 Gubkina)

Lower bounds for databases augmented with logical theories

V. V. Podolskii
Video records:
MP4 585.3 Mb
MP4 265.8 Mb

Number of views:
This page:104
Video files:12

V. V. Podolskii
Photo Gallery

Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке

Abstract: In this talk we will discuss an application of Boolean circuit complexity to the so called databases with ontology based data access. There are first-order logic predicates defined on the elements of such a database and there is a given first-order logical theory. The query to such a database is a first-order logic formula and the answer to the query is a tuple of database elements satisfying this formula. One of the main problems addressed in this field is to determine the algorithmic complexity of finding the answer to a given query in a given database. The standard approach to query answering is to reformulate a query in such a way that the answer to the query can be found based only on the values of the predicates on the database elements. The natural question arising in this approach is how large can the reformulated query be compared to the original one. We will discuss upper and lower bounds on the size of these reformulations in different settings with various restrictions on logical theories, queries and reformulations. These bounds are based on the classical results in Boolean circuit complexity. To prove these bounds we introduced a new computational model called hypergraph programs. This model is used to build a connection between databases and Boolean circuits.

Related articles:

SHARE: FaceBook Twitter Livejournal
Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021