

Conference «Contemporary Mathematics and its applications» dedicated to the results of research supported by the Russian Science Foundation grant 145000005
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 
Photo Gallery

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 firstorder logic predicates defined on the elements of such a database and there is a given firstorder logical theory. The query to such a database is a firstorder 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:

