Efficient Query answering Under UpdateS

• Applicant: Professorin Dr. Nicole Schweikardt
• Subject Area: Theoretical Computer Science
• Term: from 2019 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 431183758

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. Indeed, 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 started a systematic study of the computational complexity of query answering under updates. Several papers, including work by members of this project, started investigating the feasibility of dealing with small updates in rather simple settings, e.g., conjunctive queries or queries on tree data. 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 also work on changing databases. We are also interested in finding principled lower bounds, i.e., minimal resources that any algorithm needs. We will study these questions for several types of queries, including Boolean queries, aggregate queries, and queries that require an enumeration of its results. The overall aim of EQUUS is to establish the consideration of updates as a standard question in database theory whenever studying new classes of queries. EQUUS is organized into three scientific tasks studying different facets of query answering under updates - Task 1: Querying Graph-Structured Data, Task 2: Complex Updates, Task 3: Lower Bounds. There is also an administrative Task 4 whose role is organization and dissemination of results. EQUUS is a binational project involving partners in France and in Germany. 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; Télécom ParisTech; IMJ, Université Paris-Diderot) and in Hauts de France (CRIL, Lens; CRIStAL, Lille). EQUUS is jointly coordinated by Stefan Mengel (CNRS, France) and Nicole Schweikardt (HU Berlin).

• DFG Programme: Research Grants
• International Connection: France
• Co-Investigators: Professor Dr. Christoph Berkholz; Professor Dr. Wim Martens; Dr. Matthias Niewerth
• Cooperation Partners: Professor Dr. Antoine Amarilli; Dr. Pierre Bourhis; Professor Dr. Arnaud Durand; Dr. Stefan Mengel; Dr. Luc Segoufin