Dipartimento di Ingegneria informatica, automatica e gestionale

Speaker: Prof. Leonid Libkin (LFCS - University of Edinburgh)
When: Wednesday, May 30th, 2012, 14:00 - 15:00
Where: Aula Magna - Via Ariosto, 25, Roma

When finding exact answers to a query over a large database is
infeasible, it is natural to approximate the query by a more efficient
one that comes from a class with good bounds on the complexity of
query evaluation. In this paper we study such approximations for
conjunctive queries. These queries are of special importance in
databases, and we have a very good understanding of the classes that
admit fast query evaluation, such as acyclic, or bounded
(hyper)treewidth queries.

We define approximations of a given query Q as queries from one of
those classes that disagree with Q as little as possible. We mostly
concentrate on approximations that are guaranteed to return correct
answers. We prove that for the above classes of tractable conjunctive
queries, approximations always exist, and are at most polynomial in
the size of the original query. This follows from general results we
establish that relate closure properties of classes of conjunctive
queries to the existence of approximations.  We also show that in many
cases, the size of approximations is bounded by the size of the query
they approximate.  We establish a number of results showing how
combinatorial properties of queries affect properties of their
approximations, study bounds on the number of approximations, as well
as the complexity of finding and identifying approximations.

This is joint work with Pablo Barcelo and Miguel Romero.