ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Incremental Maintenance of Views with Duplicates.

Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
@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

Online Version (ACM WWW Account required): Full Text in PDF Format

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Michael J. Carey, Donovan A. Schneider (Eds.): Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. ACM Press 1995 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 24(2), June 1995
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1226 KB]

References

[1]
Serge Abiteboul, Victor Vianu: Equivalence and optimization of relational transactions. J. ACM 35(1): 70-120(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Implementation of Delayed Updates in Heraclitus. EDBT 1992: 261-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Timothy Griffin, Howard Trickey: Integrity Maintenance in A Telecommunications Switch. IEEE Data Eng. Bull. 17(2): 43-46(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[10]
...
[11]
Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Richard Hull, Dean Jacobs: Language Constructs for Programming Active Databases. VLDB 1991: 455-467 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
...
[26]
Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Xiaolei Qian: An Axiom System for Database Transactions. Inf. Process. Lett. 36(4): 183-189(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
Jan Van den Bussche, Jan Paredaens: The Expressive Power of Structured Values in Pure OODB's. PODS 1991: 291-299 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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)

Copyright © Mon Nov 2 21:12:08 2009 by Michael Ley (ley@uni-trier.de)