Output-Optimal Algorithms for Join-Aggregate Queries

The classic Yannakakis framework proposed in 1981 is still the state-of-the-art approach for tackling acyclic join-aggregate queries defined over commutative semi-rings. It has been shown that the time complexity of the Yannakakis framework is O (N +) for any free-connex join-aggregate query, where N is the input size of database and is the output size of the query result. This is already output-optimal. However, only a general upper bound O (N) on the time complexity of the Yannakakis framework is known for the remaining class of acyclic but non-free-connex queries. We first show a lower bound (N ^1- 1{} +) for computing an acyclic join-aggregate query by semi-ring algorithms, where is identified as the out-width of the input query, N is the input size of the database, and is the output size of the query result. For example, =2 for the chain matrix multiplication query, and =k for the star matrix multiplication query with k relations. We give a tighter analysis of the Yannakakis framework and show that Yannakakis framework is already output-optimal on the class of aggregate-hierarchical queries. However, for the large remaining class of non-aggregate-hierarchical queries, such as chain matrix multiplication query, Yannakakis framework indeed requires (N) time. We next explore a hybrid version of the Yannakakis framework and present an output-optimal algorithm for computing any general acyclic join-aggregate query within (N ^1-1{} +) time, matching the out-width-dependent lower bound up to a poly-logarithmic factor. To the best of our knowledge, this is the first polynomial improvement for computing acyclic join-aggregate queries since 1981.