"Building Relational Circuits"

by Florent Capelli

Abstract: We review two algorithms which allow to build a factorized representation of the answers set of join queries. In a nutshell, the representation builds a circuit representing the answers set of a join query by starting from atomic relations and iteratively combine them by either constructing the Cartesian product or the disjoint union of previously computed relations. The first one can be seen as the trace of the celebrated Yannakakis algorithm, building the answer set from the inputs to the output of the circuit while the second adopts a top-down approach which can be seen as a generalization of the exhaustive DPLL algorithm, originally designed to solve the #SAT problem.

Florent Capelli is a junior professor at CRIL of Université d'Artois in Lens. His research focuses on the study of aggregation problems, from enumeration to counting problems where one aims to understanding a large set of solutions without necessarely exploring it completely. He is particularly interested in problems from database theory, proof complexity and optimization. His favorite algorithmic techniques are based on data structures used in the realm of knowledge compilation which uses syntactically restricted circuits to offer trade-offs between size and tractability. He has co-authored two best newcomer papers at ICDT and regularly participates in PC for conferences in theoretical computer sciences, AI and databases.