Séminaire de Florent Capelli
DPLL is worst-case optimal
6 nov. 2025 - 14:00In database theory, a join algorithm is said to be worst case optimal for a class of databases $C$ if the time needed to compute the join of a set of tables is linear in the time needed to output the largest possible join one can have by considering databases from $C$. Many worst case optimal joins have been proposed in the literature but their analysis is often hard to understand. For some of them, knowledge of the actual value for the worst case is necessary, for others, non trivial data structures are needed. In this talk, we will show that applying an algorithm akin to DPLL for computing the join achieves worst case optimality in many database classes, and the complexity analysis is very simple and does not depend on the knowledge of the worst case value nor on any kind of data structures. If time allows, we will show how knowledge of the worst case value can then be leverage into this algorithm in order to transform it into an algorithm for sampling the answers uniformly with good complexity guarantees, matching the complexity obtained recently in more convoluted way. Our goal is to propose a modular and simple enough approach that can be taught easily.