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

@article{DBLP:journals/tods/Roussopoulos91,
  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        = {http://doi.acm.org/10.1145/111197.111215, db/journals/tods/Roussopoulos91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

• 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/An3-2 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[1]

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

[2]

Amihood Amir, Nick Roussopoulos: Optimal view caching. Inf. Syst. 15(2): 169-171(1990) BibTeX

[3]

François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX

[4]

Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX

[5]

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

[6]

Stefano Ceri, Georg Gottlob, Gio Wiederhold: Efficient Database Access from Prolog. IEEE Trans. Software Eng. 15(2): 153-164(1989) BibTeX

[7]

Stavros S. Cosmadakis, Christos H. Papadimitriou: Updates of Relational Views. J. ACM 31(4): 742-760(1984) BibTeX

[8]

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

[9]

Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX

[10]

...

[11]

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

[12]

Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX

[13]

Arthur M. Keller: The Role of Semantics in Translating View Updates. IEEE Computer 19(1): 63-73(1986) BibTeX

[14]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[15]

Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209 BibTeX

[16]

Nick Roussopoulos: The Logical Access Path Schema of a Database. IEEE Trans. Software Eng. 8(6): 563-573(1982) BibTeX

[17]

...

[18]

Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX

[19]

Nick Roussopoulos, Hyunchul Kang: Preliminary Design of ADMS±: A Workstation-Mainframe Integrated Architecture for Database Management Systems. VLDB 1986: 355-364 BibTeX

[20]

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

[21]

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

[22]

Nick Roussopoulos, Hyun Soon Kim: ROOST: A Relational Object Oriented System. FODO 1989: 404-420 BibTeX

[23]

Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX

[24]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[25]

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

[26]

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

[27]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[28]

Gio Wiederhold: Views, Objects, and Databases. IEEE Computer 19(12): 37-44(1986) BibTeX

[29]

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)