RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Video Library
Archive
Most viewed videos

Search
RSS
New in collection





You may need the following programs to see the files






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:63
Video files:9

V. V. Podolskii
Photo Gallery


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

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

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: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019