Algorithms for Deferred View Maintenance.

@inproceedings{DBLP:conf/sigmod/ColbyGLMT96,
  author    = {Latha S. Colby and
               Timothy Griffin and
               Leonid Libkin and
               Inderpal Singh Mumick and
               Howard Trickey},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Algorithms for Deferred View Maintenance},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {469-480},
  ee        = {http://doi.acm.org/10.1145/233269.233364, db/conf/sigmod/ColbyGLMT96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Materialized views and view maintenance are important for data warehouses, retailing, banking, and billing applications. We consider two related view maintenance problems: 1) how to maintain views after the base tables have already been modified, and 2) how to minimize the time for which the view is inaccessible during maintenance.

Typically, a view is maintained immediately, as a part of the transaction that updates the base table. Immediate maintenance imposes a significant overhead on update transactions that cannot be tolerated in many applications. In contrast, deferred maintenance allows a view to become inconsistent with its definition. A refresh operation is used to reestablish consistency. We present new algorithms to incrementally refresh a view during deferred maintenance. Our algorithms avoid a state bug that has artificially limited techniques previouslly used for deferred maintenance.

Incremental deferred view maintenance requires auxiliary tables that contain information recorded since the last view refresh. We present three scenarios for the use of auxiliary tables and show how these impact per-transaction overhead and view refresh time. Each scenario is described by an invariant that is required to hold in all database states. We then show that, with the proper choice of auxiliary tables, it is possible to lower both per-transaction overhead and view refresh time.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[AGK95]

Brad Adelberg, Hector Garcia-Molina, Ben Kao: Applying Update Streams in a Soft Real-Time Database System. SIGMOD Conference 1995: 245-256 BibTeX

[AL80]

Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 BibTeX

[BLT86]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[CG+96]

...

[CW91]

Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 BibTeX

[GHJ96]

Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language. ACM Trans. Database Syst. 21(3): 370-426(1996) BibTeX

[GJM96]

Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144 BibTeX

[GL95]

Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339 BibTeX

[GM93]

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX

[GM95]

Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX

[GM96]

...

[GMS93]

Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX

[Gri81]

David Gries: The Science of Programming. Springer 1981
BibTeX

[Han87]

Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 BibTeX

[KR87]

Bo Kähler, Oddvar Risnes: Extending Logging for Database Snapshot Refresh. VLDB 1987: 389-398 BibTeX

[LH+86]

Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60 BibTeX

[LW93]

Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX

[Pai84]

...

[QW91]

Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) BibTeX

[RK86]

Nick Roussopoulos, Hyunchul Kang: Principles and Techniques in the Design of ADMS±. IEEE Computer 19(12): 19-25(1986) BibTeX

[SI84]

Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 BibTeX

[SL76]

Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX

[SP89]

Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989) BibTeX

[SR88]

Jaideep Srivastava, Doron Rotem: Analytical Modeling of Materialized View Maintenance. PODS 1988: 126-134 BibTeX

[ZG+95]

Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327 BibTeX

Referenced by

1. Kenneth Salem, Kevin S. Beyer, Roberta Cochrane, Bruce G. Lindsay: How To Roll a Join: Asynchronous Incremental View Maintenance. SIGMOD Conference 2000: 129-140
2. Wilburt Labio, Ramana Yerneni, Hector Garcia-Molina: Shrinking the Warehouse Update Window. SIGMOD Conference 1999: 383-394
3. Tok Wang Ling, Eng Koon Sze: Materialized View Maintenance Using Version Numbers. DASFAA 1999: 263-270
4. Timothy Griffin, Bharat Kumar: Algebraic Change Propagation for Semijoin and Outerjoin Queries. SIGMOD Record 27(3): 22-27(1998)
5. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
6. Laks V. S. Lakshmanan, Subbu N. Subramanian, Nita Goyal, Ravi Krishnamurthy: On Query Spreadsheets. ICDE 1998: 134-141
7. Tok Wang Ling, Ye Liu: An Efficient View Maintenance Algorithm for Data Warehousing. ER Workshops 1998: 169-180
8. Tetsuya Furukawa, Fei Sha II: Reducing Algorithms for Materialized View Updates. ER 1998: 377-392
9. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
10. Inderpal Singh Mumick, Dallan Quass, Barinderpal Singh Mumick: Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997: 100-111
11. Latha S. Colby, Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Supporting Multiple View Maintenance Policies. SIGMOD Conference 1997: 405-416
12. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
13. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
14. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Dallan Quass, Kenneth A. Ross: Concurrency Control Theory for Deferred Materialized Views. ICDT 1997: 306-320
15. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
16. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221
17. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492