More Web Proxy on the site http://driver.im/

Article

Efficient incremental maintenance of data cubes

Authors:

Myoung Ho KimAuthors Info & Claims

VLDB '06: Proceedings of the 32nd international conference on Very large data bases

Pages 823 - 833

Published: 01 September 2006 Publication History

Abstract

The data cube provides users with aggregated results that are group-bys for all possible combinations of dimension attributes. When the number of dimension attributes is n, the data cube computes 2ⁿ group-bys, each of which is called a cuboid. A data cube is often precomputed and stored as materialized views in data warehouses. The data cube needs to be updated when source relations change. The incremental maintenance of a data cube is to compute and propagate only changes of source relations rather than recompute the entire data cube from the source relations.To maintain a data cube incrementally, previous methods compute a delta cube which represents the change of the data cube. We call a cuboid in a delta cube a delta cuboid. For a data cube with 2ⁿ cuboids, a delta cube consists of 2ⁿ delta cuboids. Thus, as the number of dimension attributes increases, the cost of computing the delta cube increases significantly. In this paper, we propose an incremental maintenance method for data cubes that can maintain a data cube by using only (n ⌈n/2⌉) delta cuboids. As a result, the cost of computing delta cuboids is substantially reduced. Through various experiments, we show the performance advantages of our method over the previous methods.

References

[1]

{1} S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan, and S. Sarawagi. On the Computation of Multidimensional Aggregates. In Proceedings of the VLDB Conference, pages 506-521, 1996.

Digital Library

[2]

{2} K. Beyer and R. Ramakrishnan. Bottom-Up Computation of Sparse and Iceberg CUBEs. In Proceedings of the ACM SIGMOD Conference, pages 359-370, 1999.

Digital Library

[3]

{3} S. Chaudhuri and K. Shim. Including Group-By in Query Optimization. In Proceedings of the VLDB Conference, pages 354-366, 1994.

Digital Library

[4]

{4} Z. Chen and V. Narasayya. Efficient Computation of Multiple Group By Queries. In Proceedings of the ACM SIGMOD Conference, pages 263-274, 2005.

Digital Library

[5]

{5} Y. Feng, D. Agrawal, A. E. Abbadi, and A. Metwally. Range CUBE: Efficient Cube Computation by Exploiting Data Correlation. In Proceedings of the ICDE Conference, page 658-670, 2004.

Digital Library

[6]

{6} L. R. Foulds and R. L. Graham. The Steiner Problem in Phylogeny is NP-Complete. Advances in Applied Mathematics, 3: 43-49, 1982.

Digital Library

[7]

{7} M. R. Garey and D. S. Johnson. Computers and Intractability, pages 45-76, W. H. Freeman, San Francisco, 1979.

[8]

{8} G. Graefe. Query Evaluation Techniques for Large Databases. ACM Computing Surveys, 25(2): 73-170, 1993.

Digital Library

[9]

{9} J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. In Proceedings of the ICDE Conference, pages 152-159, 1996.

Digital Library

[10]

{10} A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining Views Incrementally. In Proceedings of the ACM SIGMOD Conference, pages 157-166, 1993.

Digital Library

[11]

{11} H. Gupta and I. S. Mumick. Incremental Maintenance of Aggregate and Outerjoin Expressions. Technical Report, Stanford University, 1999.

[12]

{12} J. Han, J. Pei, G. Dong, and K. Wang. Efficient Computation of Iceberg Cubes with Complex Measures. Proceedings of the ACM SIGMOD Conference, page 1-12, 2001.

Digital Library

[13]

{13} V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing Data Cubes Efficiently. In Proceedings of the ACM SIGMOD Conference, pages 205-216, 1996.

Digital Library

[14]

{14} C. A. Hurtado, A. O. Mendelzon, and A. A. Vaisman. Maintaining Data Cubes under Dimension Updates. In Proceedings of the ICDE Conference, pages 346-355, 1999.

Digital Library

[15]

{15} Y. Kotidis. Aggregate View Management in Data Warehouses. Handbook of Massive Data Sets, pages 711-741, 2002.

Digital Library

[16]

{16} W. Lehner, R. Sidle, H. Pirahesh, and R. Cochrane. Maintenance of Cube Automatic Summary Tables. In Proceedings of the ACM SIGMOD Conference, pages 512-513, 2000.

Digital Library

[17]

{17} I. S. Mumick, D. Quass, and B. S. Mumick. Maintenance of Data Cubes and Summary Tables in a Warehouse. In Proceedings of the ACM SIGMOD Conference, pages 100-111, 1997.

Digital Library

[18]

{18} C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity, chapter 11, pages 247-254, 1982.

Digital Library

[19]

{19} D. Quass. Maintenance Expressions for Views with Aggregation. In Workshop on Materialized Views: Techniques and Applications, pages 110-118, 1996.

[20]

{20} K. A. Ross and D. Srivastava. Fast Computation of Sparse Datacubes. In Proceedings of the VLDB Conference, pages 116-125, 1997.

Digital Library

[21]

{21} N. Roussopoulos, Y. Kotidis, and M. Roussopoulos. Cubetree: Organization of and Bulk Incremental Updates on the Data Cube. In Proceedings of the ACM SIGMOD Conference, pages 89-99, 1997.

Digital Library

[22]

{22} TPC Committee. Transaction Processing Council. http://www.tpc.org/

Cited By

Liu SSong BGangam SLo LElmeleegy K(2016)KodiakProceedings of the VLDB Endowment10.14778/3007263.30072669:13(1269-1280)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.14778/3007263.3007266
Wang ZChu YTan KAgrawal DEi Abbadi A(2016)HaCubeProceedings, Part II, of the 21st International Conference on Database Systems for Advanced Applications - Volume 964310.1007/978-3-319-32049-6_8(113-129)Online publication date: 16-Apr-2016
https://dl.acm.org/doi/10.1007/978-3-319-32049-6_8
Ammendola CBöhlen MGamper J(2013)Efficient Evaluation of Ad-Hoc Range AggregatesProceedings of the 15th International Conference on Data Warehousing and Knowledge Discovery - Volume 805710.1007/978-3-642-40131-2_5(46-59)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40131-2_5
Show More Cited By

Index Terms

Efficient incremental maintenance of data cubes
1. Information systems

Recommendations

An incremental maintenance scheme of data cubes
DASFAA'08: Proceedings of the 13th international conference on Database systems for advanced applications

Data cube construction is a commonly used operation in data warehouses. Because of the volume of data stored and analyzed in a data warehouse and the amount of computation involved in data cube construction, incremental maintenance of data cube is ...
An efficient method for maintaining data cubes incrementally

The data cube operator computes group-bys for all possible combinations of a set of dimension attributes. Since computing a data cube typically incurs a considerable cost, the data cube is often precomputed and stored as materialized views in data ...
The Mobius Cubes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

VLDB '06: Proceedings of the 32nd international conference on Very large data bases

September 2006

1269 pages

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data
K.I.S.S. SIG on Databases
AJU Information Technology Co., Ltd
US Army ITC-PAC Asian Research Office
Google Inc.
The Database Society of Japan
Samsung SOS
Advanced Information Technology Research Center
Naver
Microsoft: Microsoft
Korea Info Sci Society: Korea Information Science Society
SK telecom
Systems Applications Products
ORACLE: ORACLE
International Business Management
Air Force Office of Scientific Research/Asian Office of Aerospace R&D
Kosef
Kaist
LG Electronics
CCF-DBS

Publisher

VLDB Endowment

Publication History

Published: 01 September 2006

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
610
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu SSong BGangam SLo LElmeleegy K(2016)KodiakProceedings of the VLDB Endowment10.14778/3007263.30072669:13(1269-1280)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.14778/3007263.3007266
Wang ZChu YTan KAgrawal DEi Abbadi A(2016)HaCubeProceedings, Part II, of the 21st International Conference on Database Systems for Advanced Applications - Volume 964310.1007/978-3-319-32049-6_8(113-129)Online publication date: 16-Apr-2016
https://dl.acm.org/doi/10.1007/978-3-319-32049-6_8
Ammendola CBöhlen MGamper J(2013)Efficient Evaluation of Ad-Hoc Range AggregatesProceedings of the 15th International Conference on Data Warehousing and Knowledge Discovery - Volume 805710.1007/978-3-642-40131-2_5(46-59)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40131-2_5
Shimada TTsuchida TTsuji THiguchi KPardede ETaniar DPardede E(2010)Distributed construction of data cubes from tuple streamProceedings of the 12th International Conference on Information Integration and Web-based Applications & Services10.1145/1967486.1967576(584-591)Online publication date: 8-Nov-2010
https://dl.acm.org/doi/10.1145/1967486.1967576
Lee KChung YKim M(2010)An efficient method for maintaining data cubes incrementallyInformation Sciences: an International Journal10.1016/j.ins.2009.11.037180:6(928-948)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.ins.2009.11.037
Morfonios KIoannidis Y(2010)Revisiting the cube lifecycle in the presence of hierarchiesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-009-0160-319:2(257-282)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/s00778-009-0160-3
Zhou GChen H(2009)What-if analysis in MOLAP environmentsProceedings of the 6th international conference on Fuzzy systems and knowledge discovery - Volume 210.5555/1800614.1800696(405-409)Online publication date: 14-Aug-2009
https://dl.acm.org/doi/10.5555/1800614.1800696
Zhang YZhang YXiao YWang SChen H(2009)The Tradeoff of Delta Table Merging and Re-writing Algorithms in What-If Analysis ApplicationProceedings of the Joint International Conferences on Advances in Data and Web Management10.1007/978-3-642-00672-2_24(260-272)Online publication date: 22-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00672-2_24
Tsuji TJin DHiguchi K(2008)Data compression for incremental data cube maintenanceProceedings of the 13th international conference on Database systems for advanced applications10.5555/1802514.1802592(682-685)Online publication date: 19-Mar-2008
https://dl.acm.org/doi/10.5555/1802514.1802592
Jin DTsuji TTsuchida THiguchi K(2008)An incremental maintenance scheme of data cubesProceedings of the 13th international conference on Database systems for advanced applications10.5555/1802514.1802534(172-187)Online publication date: 19-Mar-2008
https://dl.acm.org/doi/10.5555/1802514.1802534

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents