Restructuring batch view maintenance efficiently

ABSTRACT

Materialized views defined over distributed data sources are a well recognized technology for modern applications. State-of the-art incremental view maintenance requires O(<i>n</i>²) or more maintenance queries to remote data sources with <i>n</i> being the number of data sources in the view definition. In this poster, we illustrate basic ideas of novel view maintenance strategies that dramatically reduce the number of maintenance queries. Such reduction brings the tradeoff between the number of maintenance queries and the complexity of each query. These algorithms have been implemented in a working prototype system. Experimental studies illustrate major performance improvement in terms of total processing time compared with existing batch algorithms.

REFERENCES

• 1: 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
• 2: 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
• 3: Songting Chen , Bin Liu , Elke A. Rundensteiner, Multiversion-based view maintenance over distributed data sources, ACM Transactions on Database Systems (TODS), v.29 n.4, p.675-709, December 2004 [doi>10.1145/1042046.1042049]
• 4: A. Gupta and I. Mumick. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Engineering Bulletin, 18(2):3--19, 1995.
• 5: 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
• 6: Bin Liu , Songting Chen , Elke A. Rundensteiner, Batch data warehouse maintenance in dynamic environments, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584807]
• 7: B. Liu, E. A. Rundensteiner, and D. Finkel. Restructuring View Maintenance Plans for Large Update Batches. Technical Report WPI-CS-TR-03-29, WPI, 2003.
• 8: 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
• 9: 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

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
batch maintenance, grouping maintenance