Efficient Query answering Under UpdateS – EQUUS

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 has 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; it will last for 36 months. It consists of 9 researchers (4 German, 5 French) well-established in database theory but with complementary backgrounds. There will also be 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; 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).

The focus of EQUUS will be fostering collaborations between the participants in the two involved countries by financing regular meetings and visits. Particular attention will be paid to the students by allowing them extended stays in the respective other country to learn from all partners and start creating their own international network.

The results of EQUUS will be disseminated at the top conferences of the field, e.g. PODS and ICDT. Moreover, all results will also be published on open access repositories and on a project homepage.