Efficient Query answering Under UpdateS
A research project funded by
Agence Nationale de la Recherche (ANR)
and
Deutsche Forschungsgemeinschaft (DFG)
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 the topic has largely focused on static databases: when the database changes even slightly, the theoretical guarantees are often no better than the strategy that reruns the query from scratch before answering, losing all already computed information. This is in stark contrast to databases in practice that maintain indexes under updates to speed up query answering.
Only recently, the database theory community has started a systematic study of the computational complexity of query answering under updates. In the EQUUS-project, we 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 also work on changing databases. We are also interested in finding principled lower bounds, i.e., minimal resources that any algorithm needs. We study these questions for several types of queries, including Boolean queries, aggregate queries, and queries that require an enumeration of its results.
