Beyond Equi-joins: Ranking, Enumeration and Factorization
How can we efficiently represent and enumerate the results of theta-join queries? Factorization techniques have found notable success as a compact representation scheme that allows for enumeration algorithms where the results are produced incrementally after a preprocessing phase. However, these factorized representations have mainly been limited so far to equi-joins. This talk will present factorization techniques for general theta-join queries where the join conditions between relations go beyond equality. These are particularly useful for the task of ranked enumeration, where the query results are returned in the order specified by a ranking function. Perhaps surprisingly, for acyclic queries with general DNFs of inequality predicates we give asymptotic guarantees that are within a polylogarithmic factor of the best-known guarantee for equi-joins. We also target cases that occur often in practice such as a single predicate or a band-join and further improve the succinctness of our representation.
Nikolaos Tziavelis is a 3rd year PhD student at the Khoury College of Computer Sciences of Northeastern University. His research interests lie in algorithms for database query processing and distributed computing. He holds a MEng in Electrical and Computer Engineering from the National Technical University of Athens.