Efficiently evaluating and accessing the answers of queries over databases is a central problem in data management, particularly as data volumes continue to grow and queries become more complex. In the relational database model, query evaluation is complicated by the presence of joins, which may induce large intermediate results and lead to prohibitive computational costs. We explore several aspects of query evaluation and their respective computational complexity. The first aspect we consider is that of worst-case optimal join algorithms. These algorithms aim to return the answer set of a query over a database, while providing strong guarantees ensuring that the evaluation runs in time proportional to the maximum possible output size. We present a join algorithm that can be shown to be worst-case optimal in a simple and modular way. One of the advantages of our approach is the implicit data representation it induces. By improving on this representation of the answers of a query, we are able to work on finer algorithmic problems. The two main evaluation tasks we consider in this talk are direct access and uniform sampling. For uniform sampling, we show how the execution trace of our worst-case optimal join algorithm can be leveraged to sample query answers according to a uniform distribution without enumerating the full result set. For direct access, we exploit relational circuits to navigate the answer space efficiently and retrieve answers at arbitrary positions in a fixed order, extending existing approaches to broader classes of queries, including queries with negation. In both cases, the aim of our algorithms is to build the answer set of queries incrementally. We also use the structure of relational circuits to improve on the complexity of these methods.
Short Bio: I am currently finishing my PhD at University of Lille, in the D-DAL Inria team. I mainly work with Florent Capelli and Sylvain Salvati on knowledge compilation and query evaluation problems in databases. I also explore the design of algorithms for worst-case optimal join operations and probabilistic data sampling, aiming to tackle fundamental challenges in handling large datasets. One of the main research directions of my thesis has also been to try improving on the readability and simplicity of the algorithmic tools and proofs in these areas. I am also interested in extending my current results on direct access and optimal joining to dynamic databases. My PhD is part of the KCODA project, which is funded by the French ANR. The aim of this project is to explore new methods for optimisation and learning problems over large datasets.
