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.
