AJAR
Citations Over TimeTop 17% of 2016 papers
Abstract
We study a class of aggregate-join queries with multiple aggregation operators evaluated over annotated relations. We show that straightforward extensions of standard multiway join algorithms and generalized hypertree decompositions (GHDs) provide best-known runtime guarantees. In contrast, prior work uses bespoke algorithms and data structures and does not match these guarantees. We extend the standard techniques by providing a complete characterization of (1) the set of orderings equivalent to a given ordering and (2) the set of GHDs valid with respect to the given ordering, i.e., GHDs that correctly answer a given aggregate-join query when provided to (simple variants of) standard join algorithms. We show by example that previous approaches are incomplete. The key technical consequence of our characterizations is a decomposition of a valid GHD into a set of (smaller) unconstrained GHDs, i.e., into a set of GHDs of sub-queries without aggregations. Since this decomposition is comprised of unconstrained GHDs, we are able to connect to the wide literature on GHDs for join query processing, thereby obtaining improved runtime bounds, MapReduce variants, and an efficient method to find approximately optimal GHDs.
Related Papers
- Bespoke, Mdre And Challenges In Mdre In Comparison With Bespoke(2012)
- → External Barriers to User-Centred Development of Bespoke Medical Devices in the UK(2013)1 cited
- From Making the Bespoke to Manufacturing the Bespoke(2012)
- As lated tongues bespoke : popular protest in south-east England, 1790-1840(2001)
- → A bespoke model of inclusive education for new arrivals(2020)