Invited Talks

Nofar Carmeli

Technion, Israel and DI ENS, Université PSL, CNRS, Inria, France

Accessing Answers to Conjunctive Queries with Ideal Time Guarantees

(sponsored by SECAI)

When can we answer conjunctive queries with ideal time guarantees? We will start this talk by examining different kinds of query-answering tasks and the connections between them. These tasks include enumerating all answers, sampling answers without repetitions, and simulating a sorted array of the answers. From a data complexity point of view, the ideal time guarantees for these tasks are constant time per answer following a linear preprocessing (required to read the database input). Our goal is to avoid the polynomial preprocessing required to produce all answers. We will then have an example-based discussion of the complexity landscape for these tasks. In particular, we will see how self-joins, constraints and unions can play a crucial role in determining the complexity and designing efficient algorithms.

Francesca Toni

Imperial College London, United Kingdom

Anni-Yasmin Turhan

Dresden University of Technology, Germany