Abstract
θ-MDA is a flexible and efficient operator for complex ad-hoc multi-dimensional aggregation queries. It separates the specification of aggregation groups for which aggregate values are computed (base table b) and the specification of aggregation tuples from which aggregate values are computed. Aggregation tuples are subsets of the detail table r and are defined by a general θ-condition. The θ-MDA requires one scan of r, during which the aggregates are incrementally updated.
In this paper, we propose a two-step evaluation strategy for θ-MDA to optimize the computation of ad-hoc range aggregates by reducing them to point aggregates. The first step scans r and computes point aggregates as a partial intermediate result x̃, which can be done efficiently. The second step combines the point aggregates to the final aggregates. This transformation significantly reduces the number of incremental updates to aggregates and reduces the runtime from \(\mathcal{O}(|{\bf r}|\cdot|{\bf b}|)\) to \(\mathcal{O}(|{\bf r}|)\), provided that \(|{\bf b}| < \sqrt{|{\bf r}|}\) and |x̃| ≈ |b|, which is common for OLAP. An empirical evaluation confirms the analytical results and shows the effectiveness of our optimization: range queries are evaluated with almost the same efficiency as point queries.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Akinde, M., Böhlen, M.H., Chatziantoniou, D., Gamper, J.: θ-constrained multi-dimensional aggregation. Information Systems 36, 341–358 (2011)
Akinde, M., Chatziantoniou, D., Johnson, T., Kim, S.: The MD-join: An operator for complex OLAP. In: Proceedings of ICDE, Washington, DC, USA, pp. 524–533 (2001)
Akinde, M.O., Böhlen, M.H.: Generalized MD-joins: Evaluation and reduction to SQL. In: Jonker, W. (ed.) Databases in Telecommunications II. LNCS, vol. 2209, pp. 52–67. Springer, Heidelberg (2001)
Akinde, M.O., Böhlen, M.H., Johnson, T., Lakshmanan, L.V.S., Srivastava, D.: Efficient OLAP query processing in distributed data warehouses. Information Systems 28, 111–135 (2003)
Chun, S.-J., Chung, C.-W., Lee, J.-H., Lee, S.-L.: Dynamic update cube for range-sum queries. In: VLDB, pp. 521–530 (2001)
Geffner, S., Agrawal, D., Abbadi, A.E., Smith, T.R.: Relative prefix sums: An efficient approach for querying dynamic olap data cubes. In: ICDE, pp. 328–335 (1999)
Gray, J., Bosworth, A., Layman, A., Reichart, D., Pirahesh, H.: Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. In: Proceedings of ICDE, Washington, DC, USA, pp. 152–159 (1996)
Gupta, A., Harinarayan, V., Quass, D.: Aggregate-query processing in data warehousing environments. In: VLDB, pp. 358–369 (1995)
Harinarayan, V., Rajaraman, A., Ullman, J.D.: Implementing data cubes efficiently. In: Proceedings of SIGMOD, New York, NY, USA, pp. 205–216 (1996)
Ho, C.-T., Agrawal, R., Megiddo, N., Srikant, R.: Range queries in OLAP data cubes. In: Proceedings of SIGMOD, Tucson, Arizona, USA, May 13-15, pp. 73–88 (1997)
Hurtado, C.A., Mendelzon, A.O., Vaisman, A.A.: Maintaining data cubes under dimension updates. In: ICDE, pp. 346–355. IEEE Computer Society (1999)
Lee, K.Y., Kim, M.H.: Efficient incremental maintenance of data cubes. In: Proceedings of the VLDB Conference, pp. 823–833 (2006)
Lehner, W., Sidle, R., Pirahesh, H., Cochrane, R.: Maintenance of automatic summary tables. In: Proceedings of SIGMOD, pp. 512–513 (2000)
Liang, W., Wang, H., Orlowska, M.E.: Range queries in dynamic OLAP data cubes. Data Knowl. Eng. 34(1), 21–38 (2000)
Mumick, B.S., Quass, D., Mumick, B.S.: Maintenance of data cubes and summary tables in a warehouse. In: Proceedings of SIGMOD, New York, NY, USA, pp. 100–111 (1997)
Sridhar, R., Ravindra, P., Anyanwu, K.: RAPID: Enabling scalable ad-hoc analytics on the semantic web. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 715–730. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Ammendola, C., Böhlen, M.H., Gamper, J. (2013). Efficient Evaluation of Ad-Hoc Range Aggregates. In: Bellatreche, L., Mohania, M.K. (eds) Data Warehousing and Knowledge Discovery. DaWaK 2013. Lecture Notes in Computer Science, vol 8057. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40131-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-40131-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40130-5
Online ISBN: 978-3-642-40131-2
eBook Packages: Computer ScienceComputer Science (R0)