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