An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis.

Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991)
  author    = {Nick Roussopoulos},
  title     = {An Incremental Access Method for ViewCache: Concept, Algorithms,
               and Cost Analysis},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {3},
  year      = {1991},
  pages     = {535-563},
  ee        = {, db/journals/tods/Roussopoulos91.html},
  bibsource = {DBLP,}


A ViewCache is a stored collection of pointers pointing to records of underlying relations needed to materialize a view. This paper presents an Incremental Access Method (IAM) that amortizes the maintenance cost of ViewCaches over a long time period or indefinitely. Amortization is based on deferred and other update propagation strategies. A deferred update strategy allows a ViewCache to remain outdated until a query needs to selectively or exhaustively materialize the view. At that point, an incremental update of the ViewCache is performed. This paper defines a set of conditions under which incremental access to the ViewCache is cost effective. The decision criteria are based on some dynamically maintained cost parameters, which provide accurate information but require inexpensive bookkeeping.

The IAM capitalizes on the ViewCache storage organization for performing the update and the materialization of the ViewCaches in an interleaved mode using one-pass algorithms. Compared to the standard technique for supporting views that requires reexecution of the definition of the view, the IAM offers significant performance advantages. We will show that under favorable conditions, most of which depend on the size of the incremental update logs between consecutive accesses of the views, the incremental access method outperforms query modification. Performance gains are higher for multilevel ViewCaches because all the I/O and CPU for handling intermediate results are avoided.

Copyright © 1991 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 1673 KB]


Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 BibTeX
Amihood Amir, Nick Roussopoulos: Optimal view caching. Inf. Syst. 15(2): 169-171(1990) BibTeX
François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
Stefano Ceri, Georg Gottlob, Gio Wiederhold: Efficient Database Access from Prolog. IEEE Trans. Software Eng. 15(2): 153-164(1989) BibTeX
Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. J. ACM 31(4): 742-760(1984) BibTeX
Umeshwar Dayal, Philip A. Bernstein: On the Correct Translation of Update Operations on Relational Views. ACM Trans. Database Syst. 7(3): 381-416(1982) BibTeX
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129 BibTeX
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
Arthur M. Keller: The Role of Semantics in Translating View Updates. IEEE Computer 19(1): 63-73(1986) BibTeX
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209 BibTeX
Nick Roussopoulos: The Logical Access Path Schema of a Database. IEEE Trans. Software Eng. 8(6): 563-573(1982) BibTeX
Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX
Nick Roussopoulos, Hyunchul Kang: Preliminary Design of ADMS±: A Workstation-Mainframe Integrated Architecture for Database Management Systems. VLDB 1986: 355-364 BibTeX
Nick Roussopoulos, Hyunchul Kang: Principles and Techniques in the Design of ADMS±. IEEE Computer 19(12): 19-25(1986) BibTeX
Nick Roussopoulos, Hyunchul Kang: A Pipeline N-way Join Algorithm Based on the 2-way Semijoin Program. IEEE Trans. Knowl. Data Eng. 3(4): 486-495(1991) BibTeX
Nick Roussopoulos, Hyun Soon Kim: ROOST: A Relational Object Oriented System. FODO 1989: 404-420 BibTeX
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
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
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
Gio Wiederhold: Views, Objects, and Databases. IEEE Computer 19(12): 37-44(1986) BibTeX
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Christian S. Jensen: Review - The Logical Access Path Schema of a Database. ACM SIGMOD Digital Review 2: (2000)
  2. Laura M. Haas, Donald Kossmann, Ioana Ursu: Loading a Cache with Query Results. VLDB 1999: 351-362
  3. Yannis Kotidis, Nick Roussopoulos: DynaMat: A Dynamic View Management System for Data Warehouses. SIGMOD Conference 1999: 371-382
  4. Stefan Deßloch, Theo Härder, Nelson Mendonça Mattos, Bernhard Mitschang, Joachim Thomas: Advanced Data Processing in KRISYS: Modeling Concepts, Implementation Techniques, and Client/Server Issues. VLDB J. 7(2): 79-95(1998)
  5. Kristian Torp, Leo Mark, Christian S. Jensen: Efficient Differential Timeslice Computation. IEEE Trans. Knowl. Data Eng. 10(4): 599-611(1998)
  6. Alex Delis, Nick Roussopoulos: Techniques for Update Handling in the Enhanced Client-Server DBMS. IEEE Trans. Knowl. Data Eng. 10(3): 458-476(1998)
  7. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
  8. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
  9. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
  10. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
  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. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
  13. Dong Wook Kim, Myoung-Ho Kim, Yoon-Joon Lee: An Effective Tutoring Technique for fast Condition Evaluation in Active Databases. DASFAA 1997: 451-460
  14. Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)
  15. 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)
  16. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  17. Ram D. Gopal, Ram Ramesh: The Query Clustering Problem: A Set Partitioning Approach. IEEE Trans. Knowl. Data Eng. 7(6): 885-899(1995)
  18. Lars Bækgaard, Leo Mark: Incremental Computation of Time-Varying Query Expressions. IEEE Trans. Knowl. Data Eng. 7(4): 583-590(1995)
  19. 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)
  20. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  21. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  22. 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
  23. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  24. 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)
  25. Nick Roussopoulos, Nikos Economou, Antony Stamenas: ADMS: A Testbed for Incremental Access Methods. IEEE Trans. Knowl. Data Eng. 5(5): 762-774(1993)
  26. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  27. Christian S. Jensen, Leo Mark: Queries on Change in an Extended Relational Model. IEEE Trans. Knowl. Data Eng. 4(2): 192-200(1992)
  28. Alex Delis, Nick Roussopoulos: Performance and Scalability of Client-Server Database Architectures. VLDB 1992: 610-623
  29. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
  30. L. Edwin McKenzie, Richard T. Snodgrass: Evaluation of Relational Algebras Incorporating the Time Dimension in Databases. ACM Comput. Surv. 23(4): 501-543(1991)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:11 2008