Showing 2024Show all
2 papers · 1 filter
cs.DB2024
A Simple Algorithm for Worst-Case Optimal Join and Sampling
Florent Capelli, Oliver Irwin, Sylvain Salvati
We present an elementary branch and bound algorithm with a simple analysis of why it achieves worstcase optimality for join queries on classes of databases defined respectively by…
cs.DB2024
Tractable Circuits in Database Theory
Antoine Amarilli, Florent Capelli
This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We t…