[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/502585.502644acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
Article

Efficient incremental view maintenance in data warehouses

Published: 05 October 2001 Publication History

Abstract

In the data warehouse environment, the concept of a materialized view is nowadays common and important in an objective of efficiently supporting OLAP query processing. Materialized views are generally derived from select-project-join of several base relations. These materialized views need to be updated when the base relations change. Since the propagation of updates to the views may impose a significant overhead, it is very important to update the warehouse views efficiently. Though various view maintenance strategies have been discussed so far, they typically require too much access to base relations, resulting in the performance degradation.In this paper we propose an efficient incremental view maintenance strategy called delta propagation that can minimize the total size of base relations accessed by analyzing the properties of base relations. We first define the delta expression and a delta propagation tree which are core concepts of the strategy. Then, a dynamic programming algorithm that can find the optimal delta expression are proposed. We also present various experimental results that show the usefulness and efficiency of the strategy.

References

[1]
J. A. Blakeley, P. Larson, and F. W. Tompa, "Efficiently Updating Materialized Views," In Proceedings of ACM SIGMOD Conference, pp. 61-71, 1986.
[2]
S. Ceri and J. Widom, "Deriving production rules for incremental view maintenance," In Proceedings of the 7th International Conference on Very Large Databases, pp. 108-119, 1991.
[3]
A. Gupta, I. S. Mumick, and V. S. Subrahmanian, "Maintaining views incrementally," In Proceedings of ACM SIGMOD Conference, pp. 157-166, 1993.
[4]
T. Griffin and L. Libkin, "Incremental maintenance of views with duplicates," In Proceedings of ACM SIGMOD Conference, pp. 328-339, 1995.
[5]
A. Gupta and I. S. Mumick, "Maintenance of Materialized Views: Problems, Techniques, and Applications," IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, Vol. 18, No. 2, 1995.
[6]
L. S. Colby, T. Griffin, L. Libkin, I. S. Mumick, and H. Tricey, "Algorithms for deferred view maintenance," In Proceedings of ACM SIGMOD Conference, pp. 469-492, 1996.
[7]
D.Quass, 'Maintenance expressions for views with aggregation," In Workshop on Materialized Views: Techniques and Applications, June, 1996.
[8]
I. S. Mumick, D. Quass, and B. S. Mumick, "Maintenance of Data Cubes and Summary Tables in a Warehouse," In Proceedings of ACM SIGMOD Conference, 1997.
[9]
H. Gupta and IS. Mumick, "Incremental maintenance of aggregate and outerjoin," Technical Report, Stanford University, 1999.
[10]
X. Qian and G. Wiederhold, "Incremental recomputation of active relational expressions,"" IEEE Transactions on Knowledge and Data Engineering, pp. 337-341, 1991.
[11]
Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom, "View Maintenance in a Warehousing Environment," In Proceedings of ACM SIGMOD Conference, 1995.
[12]
Y. Zhuge, H. Garcia-Molina, and J. L. Wiener, "The Strobe Algorithms for Multi-Source Warehouse Consistency," In Proceedings of the International Conference on Parallel and Distributed Information Systems, December, 1996.
[13]
D. Agrawal, A. E. Abbadi, A. Singh, and T. Yurek, "Efficient View Maintenance at Data Warehouses,' In Proceedings of ACM SIGMOD Conference, 1997.
[14]
K. Salem, K. Beyer and B. Lindsay, "How To Roll a Join: Asynchronous Incremental View Maintenance," In Proceedings of ACM SIGMOD Conference, pp. 129-140, 2000.
[15]
H. Mistry, R. Roy, S. Sudarshan, K. Ramamritham, "Materialized View Selection and Maintenance Using Multi-Query Optimization," In Proceedings of ACM SIGMOD Conference, 2001.
[16]
W. J. Labio, R. Yerneni, and H. Garcia- Molina, "Shrinking the Warehouse Update Window," In Proceedings of ACM SIGMOD Conference, 1999.
[17]
J. Widom, "Research Problems in Data Warehousing," In Proceedings of 4th International Conference on Information and Knowledge Management, November, 1995.
[18]
W. H. Immon, Building the Data Warehouse, Wiley Computer Publishing, 1996.
[19]
B. Niamir, "Attribute Partitioning in a Self- Adaptive vRelational Database System," Technical Report, Cambridge, Mass.: Laboratory for Computer Science, Massachusetts Institute of Technology, 1978.
[20]
M. Hammer and B. Niamir, "A Heuristic Approach to Attribute Partitioning," In Proceedings of ACM SIGMOD Conference, pp. 93-101, 1979.
[21]
TPC Committee, Transaction Processing Council, http://www.tpc.org/

Cited By

View all
  • (2023)Change Propagation Without JoinsProceedings of the VLDB Endowment10.14778/3579075.357908016:5(1046-1058)Online publication date: 1-Jan-2023
  • (2023)Towards Scalable Process Mining Pipelines2023 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)10.1109/DASC/PiCom/CBDCom/Cy59711.2023.10361330(0175-0182)Online publication date: 14-Nov-2023
  • (2016)The Impact of Business Intelligence on Corporate Performance ManagementProceedings of the 2016 49th Hawaii International Conference on System Sciences (HICSS)10.1109/HICSS.2016.625(5042-5051)Online publication date: 5-Jan-2016
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '01: Proceedings of the tenth international conference on Information and knowledge management
October 2001
616 pages
ISBN:1581134363
DOI:10.1145/502585
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2001

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. data warehouse
  2. materialized view
  3. view maintenance

Qualifiers

  • Article

Conference

CIKM01
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)2
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Change Propagation Without JoinsProceedings of the VLDB Endowment10.14778/3579075.357908016:5(1046-1058)Online publication date: 1-Jan-2023
  • (2023)Towards Scalable Process Mining Pipelines2023 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)10.1109/DASC/PiCom/CBDCom/Cy59711.2023.10361330(0175-0182)Online publication date: 14-Nov-2023
  • (2016)The Impact of Business Intelligence on Corporate Performance ManagementProceedings of the 2016 49th Hawaii International Conference on System Sciences (HICSS)10.1109/HICSS.2016.625(5042-5051)Online publication date: 5-Jan-2016
  • (2013)Agile Development in Data WarehousingPrinciples and Applications of Business Intelligence Research10.4018/978-1-4666-2650-8.ch020(286-300)Online publication date: 2013
  • (2013)SQL optimization in a parallel processing database system2013 26th IEEE Canadian Conference on Electrical and Computer Engineering (CCECE)10.1109/CCECE.2013.6567832(1-5)Online publication date: May-2013
  • (2013)Higher-Order reactive programming with incremental listsProceedings of the 27th European conference on Object-Oriented Programming10.1007/978-3-642-39038-8_29(707-731)Online publication date: 1-Jul-2013
  • (2012)Saving DBMS Resources While Running Batch Cycles in Data WarehousesKnowledge and Technology Adoption, Diffusion, and Transfer10.4018/978-1-4666-1752-0.ch009(118-132)Online publication date: 2012
  • (2012)Incremental Load in a Data Warehousing EnvironmentInsights into Advancements in Intelligent Information Technologies10.4018/978-1-4666-0158-1.ch009(161-177)Online publication date: 2012
  • (2011)Agile Development in Data WarehousingInternational Journal of Business Intelligence Research10.4018/jbir.20110701052:3(64-77)Online publication date: 1-Jul-2011
  • (2010)NectarProceedings of the 9th USENIX conference on Operating systems design and implementation10.5555/1924943.1924949(75-88)Online publication date: 4-Oct-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media