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.