Efficient incremental view maintenance in data warehouses

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: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 2: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 3: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 4: Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States
• 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: Latha S. Colby , Timothy Griffin , Leonid Libkin , Inderpal Singh Mumick , Howard Trickey, Algorithms for deferred view maintenance, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.469-480, June 04-06, 1996, Montreal, Quebec, Canada
• 7: D.Quass, 'Maintenance expressions for views with aggregation," In Workshop on Materialized Views: Techniques and Applications, June, 1996.
• 8: Inderpal Singh Mumick , Dallan Quass , Barinderpal Singh Mumick, Maintenance of data cubes and summary tables in a warehouse, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.100-111, May 11-15, 1997, Tucson, Arizona, United States
• 9: H. Gupta and IS. Mumick, "Incremental maintenance of aggregate and outerjoin," Technical Report, Stanford University, 1999.
• 10: X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991 [doi>10.1109/69.91063]
• 11: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States
• 12: Yue Zhuge , Hector Garcia-Molina , Janet L. Wiener, The Strobe algorithms for multi-source warehouse consistency, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.146-157, December 18-20, 1996, Miami Beach, Florida, United States
• 13: D. Agrawal , A. El Abbadi , A. Singh , T. Yurek, Efficient view maintenance at data warehouses, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.417-427, May 11-15, 1997, Tucson, Arizona, United States
• 14: Kenneth Salem , Kevin Beyer , Bruce Lindsay , Roberta Cochrane, How to roll a join: asynchronous incremental view maintenance, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.129-140, May 15-18, 2000, Dallas, Texas, United States
• 15: Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham, Materialized view selection and maintenance using multi-query optimization, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.307-318, May 21-24, 2001, Santa Barbara, California, United States
• 16: Wilburt Juan Labio , Ramana Yerneni , Hector Garcia-Molina, Shrinking the warehouse update Window, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.383-394, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 17: Jennifer Widom, Research problems in data warehousing, Proceedings of the fourth international conference on Information and knowledge management, p.25-30, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221319]
• 18: W. H. Inmon, Building the data warehouse (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1996
• 19: B. Niamir, ATTRIBUTE PARTITIONING IN A SELF-ADAPTIVE RELATIONAL DATA BASE SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 20: Michael Hammer , Bahram Niamir, A heuristic approach to attribute partitioning, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582110]
• 21: TPC Committee, Transaction Processing Council, http://www.tpc.org/

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases; Query processing

General Terms:
Algorithms, Design, Management

Keywords:
data warehouse, materialized view, view maintenance