Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present incremental view maintenance algorithms for a data warehouse derived from multiple distributed autonomous data sources. We begin with a detailed framework for analyzing view maintenance algorithms for multiple data sources with concurrent updates. Earlier approaches for view maintenance in the presence of concurrent updates typically require two types of messages: one to compute the view change due to the initial update and the other to compensate the view change due to interfering concurrent updates. The algorithms developed in this paper instead perform the compensation locally by using the information that is already available at the data warehouse. The first algorithm, termed SWEEP, ensures complete consistency of the view at the data warehouse in the presence of concurrent updates. Previous algorithms for incremental view maintenance either required a quiescent state at the data warehouse or required an exponential number of messages in terms of the data sources. In contrast, this algorithm does not require that the data warehouse be in a quiescent state for incorporating the new views and also the message complexity is linear in the number of data sources. The second algorithm, termed Nested SWEEP, attempts to compute a composite view change for multiple updates that occur concurrently while maintaining strong consistency.

REFERENCES

• BCP96: Elena Baralis, Stefano Ceri, and Stefaao Parabosc2fi. Conservative Timestamp Revisited for Materialized View Maintenance in a Data Warehouse. In Workshop on VIEWS'96, 1996.
• 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
• CGL+96: 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
• 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
• GHJ96: Shahram Ghandeharizadeh , Richard Hull , Dean Jacobs, Heraclitus: elevating deltas to be first-class citizens in a database programming language, ACM Transactions on Database Systems (TODS), v.21 n.3, p.370-426, Sept. 1996 [doi>10.1145/232753.232801]
• GJM96: Ashish Gupta , H. V. Jagadish , Inderpal Singh Mumick, Data Integration using Self-Maintainable Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.140-144, March 25-29, 1996
• GL95: 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
• GM95: A. Gupta and I. S. Mumick. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Bulletin of the Technical Committee on Data Engineerin9, 18(2):3-18, june 1995.
• 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
• HGMW+95: J. Hammer, H. Garcia-Molina, J. Widom, W. Labio, and Y. Zhuge. The Stanford Data Warehousing Project. IEEE Bulletin of the Technical Committee on Data Engineering, 18(2):41-48, June 1995.
• HJ91: Richard Hull , Dean Jacobs, Language Constructs for Programming Active Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.455-467, September 03-06, 1991
• HZ96a: Richard Hull , Gang Zhou, A framework for supporting data integration using the materialized and virtual approaches, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.481-492, June 04-06, 1996, Montreal, Quebec, Canada
• HZ96b: Richard Hull and Gang Zhou. Towards the Study of Performance T~ade-offs Between Materialized and Virtual Integrated Views. In Workahop on VIEWS'96, 1996.
• QGMW96: Dallan Quass , Ashish Gupta , Inderpal Singh Mumick , Jennifer Widom, Making views self-maintainable for data warehousing, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.158-169, December 18-20, 1996, Miami Beach, Florida, 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]
• RBS96: RBS. Data Warehouse Applications. Red Brick Systems, 1996.
• 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
• Yur97: T. Yurek. Efficient View Maintenance at Data Warehouses. Master's thesis, University of California at Santa Barbara, Department of Computer Science, UCSB, Santa Barbara, CA 93106, 1997.
• ZGMHW95: 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
• ZGMW96: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory