LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Structural tractability of counting solutions to conjunctive queries
- Date
- Tuesday, November 12 2013 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Stefan Mengel (Ecole Polytechnique)
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 has any answers with respect to the database. 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.