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

Efficiently Updating Materialized Views.

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71
@inproceedings{DBLP:conf/sigmod/BlakeleyLT86,
  author    = {Jos{\'e} A. Blakeley and
               Per-{\AA}ke Larson and
               Frank Wm. Tompa},
  editor    = {Carlo Zaniolo},
  title     = {Efficiently Updating Materialized Views},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {61-71},
  ee        = {http://doi.acm.org/10.1145/16894.16861, db/conf/sigmod/BlakeleyLT86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Query processing can be sped up by keeping frequently accessed users' views materialized. However, the need to access base relations in response to queries can be avoided only if the materialized view is adequately maintained. We propose a method in which all database updates to base relations are first filtered to remove from consideration those that cannot possibly affect the view. The conditions given for the detection of updates of this type, called irrelevant updates, are necessary and sufficient and are independent of the database state. For the remaining database updates, a differential algorithm can be applied to re-evaluate the view expression. The algorithm proposed exploits the knowledge provided by both the view definition expression and the database update operations.

Copyright © 1986 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 2, SIGMOD '75-'92" and ...

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

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library


References

[AL80]
Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASU79]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BC79]
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
[F62]
...
[GSV84]
...
[HS78]
Michael Hammer, Sunil K. Sarin: Efficient Monitoring of Database Assertions (Abstract). SIGMOD Conference 1978: 159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HT85]
...
[K80]
...
[KP81]
Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[L85]
...
[M83]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RH80]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SI84]
Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WY76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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. Laks V. S. Lakshmanan, Fereidoon Sadri, Subbu N. Subramanian: On Efficiently Implementing SchemaSQL on an SQL Database System. VLDB 1999: 471-482
  3. Chaoyi Pang, Kotagiri Ramamohanarao, Guozhu Dong: Incremental FO(+, <) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions. ICDT 1999: 365-382
  4. Dominique Laurent, Jens Lechtenbörger, Nicolas Spyratos, Gottfried Vossen: Complements for Data Warehouses. ICDE 1999: 490-499
  5. Kristian Torp, Leo Mark, Christian S. Jensen: Efficient Differential Timeslice Computation. IEEE Trans. Knowl. Data Eng. 10(4): 599-611(1998)
  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. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
  8. Timothy Griffin, Bharat Kumar: Algebraic Change Propagation for Semijoin and Outerjoin Queries. SIGMOD Record 27(3): 22-27(1998)
  9. Hector Garcia-Molina, Wilburt Labio, Jun Yang: Expiring Data in a Warehouse. VLDB 1998: 500-511
  10. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
  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. Tetsuya Furukawa, Fei Sha II: Reducing Algorithms for Materialized View Updates. ER 1998: 377-392
  14. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
  15. Mala Rajamani, Karen C. Davis: Partitioned Auxiliary Views for Self-Maintainable Data Warehouses. DOLAP 1998: 66-71
  16. Uday R. Kulkarni, Richard G. Ramirez: Independently Updated Views. IEEE Trans. Knowl. Data Eng. 9(5): 798-812(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. Inderpal Singh Mumick, Dallan Quass, Barinderpal Singh Mumick: Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997: 100-111
  20. Latha S. Colby, Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Supporting Multiple View Maintenance Policies. SIGMOD Conference 1997: 405-416
  21. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
  22. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  23. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Dallan Quass, Kenneth A. Ross: Concurrency Control Theory for Deferred Materialized Views. ICDT 1997: 306-320
  24. Yue Zhuge, Hector Garcia-Molina, Janet L. Wiener: Multiple View Consistency for Data Warehousing. ICDE 1997: 289-300
  25. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
  26. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221
  27. Dong Wook Kim, Myoung-Ho Kim, Yoon-Joon Lee: An Effective Tutoring Technique for fast Condition Evaluation in Active Databases. DASFAA 1997: 451-460
  28. Rongquen Chen, Weiyi Meng: Efficient View Maintenance in a Multidatabase Environment. DASFAA 1997: 391-400
  29. Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)
  30. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
  31. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
  32. Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996)
  33. David Botzer, Opher Etzion: Optimization of Materialization Strategies for Derived Data Elements. IEEE Trans. Knowl. Data Eng. 8(2): 260-272(1996)
  34. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
  35. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492
  36. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
  37. Martin Sköld, Tore Risch: Using Partial Differencing for Efficient Monitoring of Deferred Complex Rule Conditions. ICDE 1996: 392-401
  38. Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144
  39. Brad Adelberg, Ben Kao, Hector Garcia-Molina: Database Support for Efficiently Maintaining Derived Data. EDBT 1996: 223-240
  40. Sofien Gannouni, Emmanuel Gleizer: Incremental View Maintenance for Data Warehousing. ADBIS 1996: 93-101
  41. Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995)
  42. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  43. A. Prasad Sistla, Ouri Wolfson: Temporal Triggers in Active Databases. IEEE Trans. Knowl. Data Eng. 7(3): 471-486(1995)
  44. Arie Segev, J. Leon Zhao: A Framework for Join Pattern Indexing in Intelligent Database Systems. IEEE Trans. Knowl. Data Eng. 7(6): 941-947(1995)
  45. Jan Chomicki, David Toman: Implementing Temporal Integrity Constraints Using an Active DBMS. IEEE Trans. Knowl. Data Eng. 7(4): 566-582(1995)
  46. Lars Bækgaard, Leo Mark: Incremental Computation of Time-Varying Query Expressions. IEEE Trans. Knowl. Data Eng. 7(4): 583-590(1995)
  47. Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Data Integration and Warehousing Using H2O. IEEE Data Eng. Bull. 18(2): 29-40(1995)
  48. Nick Roussopoulos, Chung-Min Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou: The ADMS Project: View R Us. IEEE Data Eng. Bull. 18(2): 19-28(1995)
  49. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  50. Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327
  51. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
  52. Brad Adelberg, Hector Garcia-Molina, Ben Kao: Applying Update Streams in a Soft Real-Time Database System. SIGMOD Conference 1995: 245-256
  53. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
  54. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
  55. Vladimir Yu. Sazonov, Alexei Lisitsa: Delta-Languages for Sets and sub-PTIME Graphs Transformers. ICDT 1995: 125-138
  56. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  57. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  58. Wei Sun, Mark Allen Weiss: An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities. IEEE Trans. Knowl. Data Eng. 6(6): 997-1001(1994)
  59. Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases: Design, Realization, and Evaluation. IEEE Trans. Knowl. Data Eng. 6(4): 587-608(1994)
  60. Rakesh Agrawal, H. V. Jagadish: Algorithms for Searching Massive Graphs. IEEE Trans. Knowl. Data Eng. 6(2): 225-238(1994)
  61. Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336
  62. Richard T. Snodgrass, Santiago Gomez, L. Edwin McKenzie: Aggregates in the Temporal Query Language TQuel. IEEE Trans. Knowl. Data Eng. 5(5): 826-842(1993)
  63. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Coupling Production Systems and Database Systems: A Homogeneous Approach. IEEE Trans. Knowl. Data Eng. 5(2): 240-256(1993)
  64. Nick Roussopoulos, Nikos Economou, Antony Stamenas: ADMS: A Testbed for Incremental Access Methods. IEEE Trans. Knowl. Data Eng. 5(5): 762-774(1993)
  65. Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
  66. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  67. Douglas B. Terry, David Goldberg, David A. Nichols, Brian M. Oki: Continuous Queries over Append-Only Databases. SIGMOD Conference 1992: 321-330
  68. V. Srinivasan, Michael J. Carey: Compensation-Based On-Line Query Processing. SIGMOD Conference 1992: 331-340
  69. Yu-Wang Wang, Eric N. Hanson: A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions. ICDE 1992: 88-97
  70. Frank Olken, Doron Rotem: Maintenance of Materialized Views of Sampling Queries. ICDE 1992: 632-641
  71. Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991)
  72. Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991)
  73. Christian S. Jensen, Leo Mark, Nick Roussopoulos: Incremental Implementation Model for Relational Databases with Transaction Time. IEEE Trans. Knowl. Data Eng. 3(4): 461-473(1991)
  74. Michael J. Carey, Rajiv Jauhari, Miron Livny: On Transaction Boundaries in Active Databases: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 3(3): 320-336(1991)
  75. Arie Segev, J. Leon Zhao: Data Management for Large Rule Systems. VLDB 1991: 297-307
  76. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589
  77. Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87
  78. Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases. SIGMOD Conference 1991: 258-267
  79. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
  80. Jean-Claude Mamou, Claudia Bauzer Medeiros: Interactive Manipulation of Object-oriented Views. ICDE 1991: 60-69
  81. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  82. W. Kevin Wilkinson, Marie-Anne Neimat: Maintaining Consistency of Client-Cached Data. VLDB 1990: 122-133
  83. Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290
  84. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
  85. Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520
  86. Daniel P. Miranker, David A. Brant: An Algorithmic Basis for Integrating Production Systems and Large Databases. ICDE 1990: 353-360
  87. José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
  88. Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421
  89. José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989)
  90. Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989)
  91. Arnon Rosenthal, Sharma Chakravarthy, Barbara T. Blaustein, José A. Blakeley: Situation Monitoring for Active Databases. VLDB 1989: 455-464
  92. Tore Risch: Monitoring Database Objects. VLDB 1989: 445-453
  93. Xian-He Sun, Nabil Kamel, Lionel M. Ni: Solving Implication Problems in Database Applications. SIGMOD Conference 1989: 185-192
  94. Eugene J. Shekita, Michael J. Carey: Performance Enhancement Through Replication in an Object-Oriented DBMS. SIGMOD Conference 1989: 325-336
  95. Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262
  96. Heikki Mannila, Kari-Jouko Räihä: Practical Algorithms for Finding Prime Attributes and Testing Normal Forms. PODS 1989: 128-133
  97. Charles Elkan: A Decision Procedure for Conjunctive Query Disjointness. PODS 1989: 134-139
  98. Arie Segev, Jooseok Park: Maintaining Materialized Views in Distributed Databases. ICDE 1989: 262-270
  99. Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383
  100. Arding Hsu, Tomasz Imielinski: View Maintenance for Multiple Updates. DASFAA 1989: 233-239
  101. Nobuhiro Ajitomi, Hiroyasu Kurose: An Enhanced RETE Algorithm for Large Scale Data Access. DASFAA 1989: 117-124
  102. Jaideep Srivastava, Doron Rotem: Precision-Time Tradeoffs: A Paradigm for Processing Statistical Queries on Databases. SSDBM 1988: 226-245
  103. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412
  104. Eric N. Hanson: Processing Queries Against Database Procedures: A Performance Analysis. SIGMOD Conference 1988: 295-302
  105. Jaideep Srivastava, Doron Rotem: Analytical Modeling of Materialized View Maintenance. PODS 1988: 126-134
  106. M. E. Iofinova, E. A. Komissartschik: Update in Hierarchical Data Bases. ICDT 1988: 292-306
  107. Michael Stonebraker, Jeff Anton, Eric N. Hanson: Extending a Database System with Procedures. ACM Trans. Database Syst. 12(3): 350-376(1987)
  108. Kazimierz Subieta, Wiktor Rzeczkowski: Query Optimization by Stored Queries. VLDB 1987: 369-380
  109. Bo Kähler, Oddvar Risnes: Extending Logging for Database Snapshot Refresh. VLDB 1987: 389-398
  110. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
  111. Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453
  112. Michael Stonebraker, Eric N. Hanson, Chin-Heng Hong: The Design of the Postgres Rules System. ICDE 1987: 365-374
  113. José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466

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