– ENUM

Ce projet concerne l'algorithmique et la complexité de l'énumération, tâche qui consiste à générer l'ensemble des solutions d'un problème donné. Pour énumérer efficacement, il est nécessaire de concevoir des algorithmes innovants qui permettent d'obtenir rapidement un large ensemble de solutions sur demande. Précalculer l'ensemble des réponses est infaisable - aussi bien en théorie qu'en pratique - si celui-ci est de grande taille. De même, générer dynamiquement l'ensemble des réponses peut s'avérer long et doit être évité autant que possible. Enumérer efficacement est une problématique naturelle de nombreux domaines de l'informatique. Une application majeure est l'évaluation de requête en base de données où des ensembles de solutions de grandes taille apparaissent naturellement. La résolution de contraintes, la combinatoire et l'algorithmique constituent aussi des domaines d'application naturels. Des algorithmes récents ont été développés qui permettent d'obtenir toutes les solutions d'une requête relationnelle avec un délai constant entre deux solutions consécutives. Cet axe de recherche, prometteur, qui en est à ses débuts, est devenu très actif ces deux dernières années et a mené à publication dans des conférences et journaux de premier plan. Des questions intéressantes en lien avec cette problématique commencent à se poser dans d'autres domaines, en évaluation de requêtes semi-structuré pour XML, par exemple. Des algorithmes d'énumération récents s'avèrent cruciaux en optimisation pour les BD XML. - - L'étude de la complexité des problèmes d'énumération doit prendre en compte un certain équilibre entre le temps de précalcul (i.e. le temps nécessaire pour obtenir la première solution) et le délai d'énumération une par une des solutions (délai que l'on souhaite le plus court possible). Ces contraintes posent de nombreuses questions fondamentales dont très peu ont été traitées de façon satisfaisante jusqu'à maintenant. Dans ce projet nous proposons de développer de nouveaux algorithmes fondamentaux pour les problèmes d'énumération et de les appliquer à l'évaluation de requêtes relationnelles mais aussi semi-structurées. Simultanément, nous souhaitons développer la théorie de la complexité des problèmes d'énumération, théorie qui n'existe quasiment pas jusqu'à aujourd'hui. Ces trois aspects - algorithmes fondamentaux, algorithmes relevant d'un domaine d'application, théorie de la complexité) doivent être entrelassés. En regardant systématiquement des problèmes d'énumération variés en base de données, nous espérons faire émerger les bonnes notions de complexité à étudier. Réciproquement, nous pensons que de nouveaux progrès en complexité sur ce sujet peuvent avoir des conséquences intéressantes sur la conception d'algorithmes d'énumération. Nous souhaitons donc étudier les points qui suivent plus particulièrement : - 1) Complexité des problèmes d'énumération. La théorie de la complexité pour ces problèmes est à construire. Même les questions les plus essentielles n'ont pas reçu une réponse satisfaisante jusque là. Les plus importantes concernent les notions de complexité appropriées : les réductions entre problèmes qui préservent les bonnes propriétés d'énumération (ou transfèrent la difficulté ), les classes de complexité, leur problèmes complets et leurs relations avec les classes de complexité classiques, la frontière entre problèmes faciles et problèmes difficiles etc. - 2) Algorithmes d'énumération pour requêtes en logique. L'énumération de requêtes du premier ordre ou du second ordre monadique est difficile en général puisqu'elle généralise des problèmes de décision déjà difficiles. Une façon d'obtenir des algorithmes d'énumération satisfaisant est de restreindre soit le langage de requête soit les modèles. Nous voulons clarifier là aussi la frontière entre problèmes faciles et difficiles. Dans cette direction, des techniques logiques mises au point par des membres du groupe semblent prometteuses. - 3) Algorithmes d