ANR PRCI EQUUS
Efficient Query answering Under UpdateS
Efficient query answering, i.e., computing the answer to a query on a given database, is one of the core problems studied in database theory. It is a very fruitful area of research with a long history and many new results and directions, e.g. efficient algorithms for aggregation, enumeration of query answers, and provenance computation. Although in practice databases are dynamic objects changing over time, the theoretical research on this topic has largely focused on static databases: when the database changes even slightly, the algorithms have to be rerun from scratch before answering, losing all already computed information. In this project, we will systematically study how and to which extent recomputation can be avoided by data structures that can be efficiently maintained after updates to the data. We are interested in finding provable efficiency guarantees on algorithms that work on changing databases, and we are interested in finding principled lower bounds, i.e., minimal resources that any algorithm needs.
EQUUS is a binational project involving partners in France and in Germany and that will last 36 months. It consists of 9 researchers (4 German, 5 French) working in database theory plus two PhD students funded by the project, one on each side. The German participants are located at Humboldt-Universität zu Berlin and Universität Bayreuth while the French participants are located in the Paris region (Inria Paris, ENS; Télécom ParisTech; IMJ, Université Paris-Diderot) and in Hauts de France (CRIL, Lens; CRIStAL, Lille).