Incremental Maintenance of Views with Duplicates.

@inproceedings{DBLP:conf/sigmod/GriffinL95,
  author    = {Timothy Griffin and
               Leonid Libkin},
  editor    = {Michael J. Carey and
               Donovan A. Schneider},
  title     = {Incremental Maintenance of Views with Duplicates},
  booktitle = {Proceedings of the 1995 ACM SIGMOD International Conference on
               Management of Data, San Jose, California, May 22-25, 1995},
  publisher = {ACM Press},
  year      = {1995},
  pages     = {328-339},
  ee        = {http://doi.acm.org/10.1145/223784.223849, db/conf/sigmod/sigmod95-26.html},
  crossref  = {DBLP:conf/sigmod/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study the problem of efficient maintenance of materialized views that may contain duplicates. This problem is particularly important when queries against such views involve aggregate functions, which need duplicates to produce correct results. Unlike most work on the view maintenance problem that is based on an algorithmic approach, our approach is algebraic and based on equational reasoning. This approach has a number of advantages: it is robust and easily extendible to new language constructs, it produces output that can be used by query optimizers, and it simplifies correctness proofs.

We use a natural extension of the relational algebra operations to bags (multisets) as our basic language. We present an algorithm that propagates changes from base relations to materialized views. This algorithm is based on reasoning about equivalence of bag-valued expressions. We prove that it is correct and preserves a certain notion of minimality that ensures that no unnecessary tuples are computed. Although it is generally only a heuristic that computing changes to the view rather than recomputing the view from scratch is more efficient, we prove results saying that under normal circumstances one should expect, the change propagation algorithm to be significantly faster and more space efficient than complete recomputing of the view. We also show that our approach interacts nicely with aggregate functions, allowing their correct evaluation on views that change.

Copyright © 1995 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

[1]

Serge Abiteboul, Victor Vianu: Equivalence and optimization of relational transactions. J. ACM 35(1): 70-120(1988) BibTeX

[2]

Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219 BibTeX

[3]

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

[4]

Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) BibTeX

[5]

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

[6]

Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou: On Implementing a Language for Specifying Active Database Execution Models. VLDB 1993: 441-454 BibTeX

[7]

Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Implementation of Delayed Updates in Heraclitus. EDBT 1992: 261-276 BibTeX

[8]

Timothy Griffin, Howard Trickey: Integrity Maintenance in A Telecommunications Switch. IEEE Data Eng. Bull. 17(2): 43-46(1994) BibTeX

[9]

...

[10]

...

[11]

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

[12]

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

[13]

Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Natural Tool to Handle Nested Database Relations. J. Comput. Syst. Sci. 45(1): 76-103(1992) BibTeX

[14]

Richard Hull, Dean Jacobs: Language Constructs for Programming Active Databases. VLDB 1991: 455-467 BibTeX

[15]

...

[16]

Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258 BibTeX

[17]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX

[18]

Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 BibTeX

[19]

...

[20]

Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX

[21]

Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) BibTeX

[22]

Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166 BibTeX

[23]

Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX

[24]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX

[25]

...

[26]

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

[27]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[28]

Xiaolei Qian: An Axiom System for Database Transactions. Inf. Process. Lett. 36(4): 183-189(1990) BibTeX

[29]

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

[30]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[31]

Jan Van den Bussche, Jan Paredaens: The Expressive Power of Structured Values in Pure OODB's. PODS 1991: 291-299 BibTeX

Referenced by

1. Wilburt Labio, Ramana Yerneni, Hector Garcia-Molina: Shrinking the Warehouse Update Window. SIGMOD Conference 1999: 383-394
2. Yannis Kotidis, Nick Roussopoulos: DynaMat: A Dynamic View Management System for Data Warehouses. SIGMOD Conference 1999: 371-382
3. Dominique Laurent, Jens Lechtenbörger, Nicolas Spyratos, Gottfried Vossen: Complements for Data Warehouses. ICDE 1999: 490-499
4. Dimitri Theodoratos: Detecting Redundancy in Data Warehouse Evolution. ER 1999: 340-353
5. Tok Wang Ling, Eng Koon Sze: Materialized View Maintenance Using Version Numbers. DASFAA 1999: 263-270
6. Harumi A. Kuno, Elke A. Rundensteiner: Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(5): 768-792(1998)
7. Timothy Griffin, Bharat Kumar: Algebraic Change Propagation for Semijoin and Outerjoin Queries. SIGMOD Record 27(3): 22-27(1998)
8. Hector Garcia-Molina, Wilburt Labio, Jun Yang: Expiring Data in a Warehouse. VLDB 1998: 500-511
9. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
10. Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258
11. Kousha Etessami: Dynamic Tree Isomorphism via First-Order Updates. PODS 1998: 235-243
12. Sameer Mahajan, Michael J. Donahoo, Shamkant B. Navathe, Mostafa H. Ammar, Sanjoy Malik: Grouping Techniques for Update Propagation in Intermittently Connected Databases. ICDE 1998: 46-53
13. Jun Yang, Jennifer Widom: Maintaining Temporal Views over Non-Temporal Information Sources for Data Warehousing. EDBT 1998: 389-403
14. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
15. Michael O. Akinde, Ole Guttorm Jensen, Michael H. Böhlen: Minimizing Detail Data in Data Warehouses. EDBT 1998: 293-307
16. Timothy Griffin, Leonid Libkin, Howard Trickey: An Improved Algorithm for the Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 9(3): 508-511(1997)
17. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
18. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
19. Dallan Quass, Jennifer Widom: On-Line Warehouse View Maintenance. SIGMOD Conference 1997: 393-404
20. Inderpal Singh Mumick, Dallan Quass, Barinderpal Singh Mumick: Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997: 100-111
21. Latha S. Colby, Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Supporting Multiple View Maintenance Policies. SIGMOD Conference 1997: 405-416
22. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
23. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
24. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Dallan Quass, Kenneth A. Ross: Concurrency Control Theory for Deferred Materialized Views. ICDT 1997: 306-320
25. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
26. Latha S. Colby, Leonid Libkin: Tractable Iteration Mechanisms for Bag Languages. ICDT 1997: 461-475
27. Yue Zhuge, Hector Garcia-Molina, Janet L. Wiener: Multiple View Consistency for Data Warehousing. ICDE 1997: 289-300
28. Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288
29. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
30. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221
31. Dan Suciu: Query Decomposition and View Maintenance for Query Languages for Unstructured Data. VLDB 1996: 227-238
32. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
33. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492
34. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
35. Sofien Gannouni, Emmanuel Gleizer: Incremental View Maintenance for Data Warehousing. ADBIS 1996: 93-101
36. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)