Tutte colloquium-Xiao Hu
Title:What is New in Join-Aggregate Query Processing?
Speaker: | Xiao Hu |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: Join-aggregate queries defined over commutative semirings subsume a wide variety of common algorithmic problems, such as graph pattern matching, graph colorability, matrix multiplication, and constraint satisfaction problems. Developing efficient algorithms for computing join-aggregate queries in the conventional RAM model has been a holy grail in database theory. One of the most celebrated results in this area is the Yannakakis algorithm dating back to 1981. Despite its prominence as a textbook solution, no improvements in its complexity have been made over the past 40 years. In this talk, I will present the first algorithm that improves upon Yannakakis for computing acyclic join-aggregate queries. Moreover, this algorithm is proven to be output-optimal among all combinatorial algorithms. One application is an output-optimal algorithm for chain matrix multiplication over sparse matrices. Beyond combinatorial algorithms, I will also show how fast matrix multiplication can further speed up the processing of conjunctive queries, a critical subclass of join-aggregate queries. Finally, I will highlight a few interesting open problems in this area.