ANR PRCI EQUUS

Réponse Efficace aux Requêtes en cas de Mises à jour

La réponse efficace aux requêtes, est l’un des principaux problèmes étudiés en théorie des bases de données. Il s’agit d’un domaine de recherche très fructueux avec une longue histoire et de nombreux nouveaux résultats et directions. On a par exemple des algorithmes efficaces pour l’agrégation, l’énumération des réponses aux requêtes et le calcul de la provenance. Bien qu’en pratique les bases de données soient des objets dynamiques changeant au fil du temps, la recherche théorique sur ce sujet s’est largement concentrée sur les bases de données statiques : lorsque la base de données change, même légèrement, les algorithmes doivent être réexécutés à partir de zéro avant de répondre, perdant ainsi toutes les informations déjà calculées. Dans ce projet, nous étudierons systématiquement comment et dans quelle mesure le recalcul peut être évité par des structures de données qui peuvent être maintenues efficacement après des mises à jour des données. Nous recherchons des garanties d’efficacité prouvables pour les algorithmes qui fonctionnent sur des bases de données changeantes, et à minimiser les ressources dont ils ont besoin.

EQUUS est un projet binational impliquant des partenaires en France et en Allemagne et qui durera 36 mois. Il est composé de 9 chercheurs (4 allemands, 5 français) travaillant sur la théorie des bases de données et de deux doctorants financés par le projet, un de chaque côté. Les participants allemands sont situés à Humboldt-Universität zu Berlin et à Universität Bayreuth tandis que les participants français sont situés en région parisienne (Inria Paris, ENS ; Télécom ParisTech ; IMJ, Université Paris-Diderot) et dans les Hauts de France (CRIL, Lens ; CRIStAL, Lille).