Titre :  Structural tractability of counting solutions to conjunctive queries

Exposant : Stefan Mengel

Résumé :  
Conjunctive queries are a basic class of database queries equivalent to select-project-join queries and strongly related to constraint satisfaction problems. Most research on conjunctive queries has focused on the so-called boolean conjunctive query problem, short CQ, which is, given a query and a database, to decide if the query answer is non-empty. While CQ is hard in general, many 'islands of tractability' have been found based on the hypergraphs associated to queries. Recently, Pichler and Skritek have shown that these hypergraph based techniques are not sufficient to guarantee tractability for the associated counting problem #CQ, i.e., given a conjunctive query and a database, determine the number of answers to the query.

I will give a short introduction into conjunctive queries and present joint work with Arnaud Durand in which we characterized exactly the tractability frontier for #CQ for well-known hypergraph based classes of conjunctive queries.