Fellows Logic Open Seminar

Efficient Approximations of Conjunctive Queries

The evaluation problem for conjunctive queries is NP-complete in general, but several restrictions have been introduced that lead to efficient evaluation (e.g., queries of bounded treewidth). Then a natural question is whether it is possible to approximate a general conjunctive query by one from those efficient restricted classes. In this talk I will present two notions of approximation for conjunctive queries: underapproximations and overapproximations. These two notions are static in the sense that they only depend on the query. I will present some basic properties of these approximations, as well as some open problems. I will also discuss non-static approximations that take into account information about the data.