View maintenance in a warehousing environment

ABSTRACT

A warehouse is a repository of integrated information drawn from remote data sources. Since a warehouse effectively implements materialized views, we must maintain the views as the data sources are updated. This view maintenance problem differs from the traditional one in that the view definition and the base data are now decoupled. We show that this decoupling can result in anomalies if traditional algorithms are applied. We introduce a new algorithm, ECA (for "Eager Compensating Algorithm"), that eliminates the anomalies. ECA is based on previous incremental view maintenance algorithms, but extra "compensating" queries are used to eliminate anomalies. We also introduce two streamlined versions of ECA for special cases of views and updates, and we present an initial performance study that compares ECA to a view recomputation algorithm in terms of messages transmitted, data transferred, and I/O costs.

REFERENCES

• BGMS92: Yuri Breitbart , Hector Garcia-Molina , Avi Silberschatz, Overview of multidatabase transaction management, The VLDB Journal — The International Journal on Very Large Data Bases, v.1 n.2, p.181-240, October 1992 [doi>10.1007/BF01231700]
• BLT86: 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
• CW91: 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
• GB94: Ashish Gupta and J. A. Blakeley. Updating materialized views using the view contents and the update. In unpublished document, 1994.
• GMS93: 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
• Han87: Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States
• HD92: J.V. Harrison and S.W. Dietrich. Maintenance of materialized views in a deductive database: An update propagation approach. In Proceedings of the 1992 JICLSP Workshop on Deductzve Databases, pages 56-65, 1992.
• IK93: W. H. Inmon , Chuck Kelley, Rdb/VMS: developing the data warehouse, John Wiley & Sons, Inc., New York, NY, 1993
• LHM+86: Bruce Lindsay , Laura Haas , C. Mohan , Hamid Pirahesh , Paul Wilms, A snapshot differential refresh algorithm, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.53-60, May 28-30, 1986, Washington, D.C., United States
• QW91: 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]
• RK86: Nick Roussopoulos , Hyunchul Kang, Preliminary Design of ADMS±: A Workstation-Mainframe Integrated Architecture for Database Management Systems, Proceedings of the 12th International Conference on Very Large Data Bases, p.355-364, August 25-28, 1986
• SF90: Arie Segev , Weiping Fang, Currency-Based Updates to Distributed Materialized Views, Proceedings of the Sixth International Conference on Data Engineering, p.512-520, February 05-09, 1990
• SF91: Arie Segev , Weiping Fang, Optimal update policies for distributed materialized views, Management Science, v.37 n.7, p.851-870, July 1991 [doi>10.1287/mnsc.37.7.851]
• SI84: Oded Shmueli , Alon Itai, Maintenance of views, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• SP89a: Arie Segev , Jooseok Park, Maintaining Materialized Views in Distributed Databases, Proceedings of the Fifth International Conference on Data Engineering, p.262-270, February 06-10, 1989
• SP89b: A. Segev , J. Park, Updating Distributed Materialized Views, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.173-184, June 1989 [doi>10.1109/69.87958]
• TB88: F. W. Tompa , J. A. Blakeley, Maintaining materialized views without accessing base data, Information Systems, v.13 n.4, p.393-406, Oct. 1, 1988 [doi>10.1016/0306-4379(88)90005-1]
• ZGMHW94: Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom. View maintenance in a warehousing environment. Technical report, Stanford University, October 1994. Available via anonymous ftp from host db'stanf~rd'edu as pub/zhuge/1994/anomaly-full, ps.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance, Verification