Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Structural tractability of counting solutions to conjunctive queries

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

 Stefan Mengel
Date
Le mardi 12 novembre 2013 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
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.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents