Ontology-based data access meets circuit complexity

Ontology-based data access is an approach to organizing access to a database augmented with a logical theory. In this approach, query answering proceeds through a reformulation of a given query into a new one which can be answered without any use of theory. Thus the query answering problem reduces to the standard database setting. However, there are computational difficulties arising in this approach: size of the query may increase substantially during the reformulation. We will discuss how Boolean Circuit Complexity helps to shed a light on these problems.