Database Seminar: Paris Koutris (University of Wisconsin-Madison) – “Join Queries with Negation (and Aggregation)”

Speaker: Paris Koutris (University of Wisconsin-Madison)

Location: Soda 380

Date: October 25, 2023

Time: 11 AM – 12 PM PST


The last decades have seen a lot of progress on our understanding of join processing, resulting in faster join algorithms and novel join techniques. In this talk, I will focus on what happens if we add negation to joins. I will start with some background and prior work, and then present a recent result that gives a tight characterization on the class of queries that admit linear-time algorithms. Then, I will extend our results to negation with aggregation, with a surprising appearance of the Ackermann function. 

Bio: Paris Koutris is an associate professor in Computer Sciences at the University of Wisconsin-Madison. His research lies in the intersection of data management theory and practice, focusing on data processing for massively parallel systems, uncertain data, and join processing. He has won the SIGMOD Jim Gray Dissertation Award for his work on the foundations of parallel data processing and was recently awarded the PODS 2023 Test-of-Time award.