Séminaire

Étant donné une requêtes q et une base de données D on souhaite calculer q(D), l'ensemble des solutions pour q sur D. Cela peut être la liste des trains allant de Paris à Clermont le 15 mars, les numéros de téléphone de tous les Dupont habitant à Paris, etc.
Le problème est que la taille de cet ensemble peut être titanesque, parfois supérieur a la taille de la base de données elle même. Par exemple le nombre de panier qu'on peux remplir avec 10€ dans un magasin peut être bien plus grand que le nombre d'articles du magasin.

Calculer l'ensemble de solutions n'est donc pas toujours réalisable. À la place, on se propose de calculer les solutions une par une, en minimisant le temps d'attente entre la production de deux solutions consécutive (le délai). Idéalement on souhaiterais que le délai soit constant (ne dépende pas de la taille de la base de donnée).
Malheureusement, de tels algorithmes ne peuvent pas exister dans le cas général. On s’intéresse alors à certaines restrictions sur les bases de données qui permettent une énumération efficace. ex: graphes de degré borné, arbres, graphes planaires etc ...

Dans la première partie de l'exposé on perlera d'algorithmes d'énumération avec divers exemples. Je présenterais également des résultats voisins pour situer nos récents travaux dans le paysage actuel.

Dans la seconde partie, on rentrera plus dans les détails de nos résultats. Je parlerais plus précisément de ces graphes nulle part dense avec les différentes définitions et des exemples. Je parlerais aussi plus en détail des parts les plus importantes de notre algorithme.