Semantic Data Caching and Replacement.

Shaul Dar, Michael J. Franklin, Björn Þór Jónsson, Divesh Srivastava, Michael Tan: Semantic Data Caching and Replacement. VLDB 1996: 330-341
  author    = {Shaul Dar and
               Michael J. Franklin and
               Bj{\"o}rn TH{\'o}r J{\'o}nsson and
               Divesh Srivastava and
               Michael Tan},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Semantic Data Caching and Replacement},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {330-341},
  ee        = {db/conf/vldb/DarFJST96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP,}


We propose a semantic model for client-side caching and replacement in a client/server database system, and study the benefits of this approach over page- and tuple-based caching/replacement strategies. Our semantic caching model is based on, and derives its advantages from, three key ideas:

First, the client maintains a semantic description of the data in its cache, instead of maintaining a list of physical pages or tuple identifiers. This allows for a compact specification, as a *remainder query*, of the tuples in the server database, not available in the client cache, needed to answer a query. Remainder queries provide reduced communication requirements and additional parallelism compared to faulting-based approaches.

Second, usability information is maintained in an adaptive fashion for *semantic regions*, which are associated with collections of tuples. This avoids the high overheads of the tuple-based approach of maintaining usability information on a per-tuple basis and, unlike the page-based approach, is also insensitive to bad clustering of tuples on pages.

Third, maintaining a semantic description of the data in the client cache encourages the use of sophisticated value functions, not just LRU or MRU, in determining usability information. Value functions that incorporate semantic notions of locality can be devised for traditional query-based applications as well as for emerging applications such as mobile databases, where query profiles have considerable regularity.

We validate these ideas with a detailed performance study that is focused initially on traditional workloads, and is then extended to workloads inspired by a mobile navigation application.

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents BibTeX

Electronic Edition


Kurt P. Brown: PRPL: A Database Workload Specification Language, v1.3. M.S. thesis, Univ. of Wisconsin-Madison 1992
Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling: Shoring Up Persistent Applications. SIGMOD Conference 1994: 383-394 BibTeX
Michael J. Carey, Michael J. Franklin, Markos Zaharioudakis: Fine-Grained Sharing in a Page Server OODBMS. SIGMOD Conference 1994: 359-370 BibTeX
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX
George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221 BibTeX
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 BibTeX
David J. DeWitt, Philippe Futtersack, David Maier, Fernando Vélez: A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems. VLDB 1990: 107-121 BibTeX
Michael J. Franklin: Client Data Caching: A Foundation for High Performance Object Oriented Database Systems. Kluwer 1996, ISBN 0-7923-9701-0
Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160 BibTeX
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 BibTeX
Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996) BibTeX
Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438 BibTeX
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
James O'Toole, Liuba Shrira: Hybrid Caching for Large-Scale Object Systems. POS 1994: 99-114 BibTeX
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) BibTeX
Nick Roussopoulos, Hyunchul Kang: Principles and Techniques in the Design of ADMS±. IEEE Computer 19(12): 19-25(1986) BibTeX
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 BibTeX

Referenced by

  1. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  2. Olga Kapitskaia, Raymond T. Ng, Divesh Srivastava: Evolution and Revolutions in LDAP Directory Caches. EDBT 2000: 202-216
  3. Prasad Deshpande, Jeffrey F. Naughton: Aggregate Aware Caching for Multi-Dimensional Queries. EDBT 2000: 167-182
  4. Kaladhar Voruganti, M. Tamer Özsu, Ronald C. Unrau: An Adaptive Hybrid Server Architecture for Client Caching ODBMSs. VLDB 1999: 150-161
  5. Laura M. Haas, Donald Kossmann, Ioana Ursu: Loading a Cache with Query Results. VLDB 1999: 351-362
  6. Daniela Florescu, Alon Y. Levy, Dan Suciu, Khaled Yagoub: Optimization of Run-time Management of Data Intensive Web-sites. VLDB 1999: 627-638
  7. Yannis Kotidis, Nick Roussopoulos: DynaMat: A Dynamic View Management System for Data Warehouses. SIGMOD Conference 1999: 371-382
  8. Sophie Cluet, Olga Kapitskaia, Divesh Srivastava: Using LDAP Directory Caches. PODS 1999: 273-284
  9. Parke Godfrey, Jarek Gryz: View Disassembly. ICDT 1999: 417-434
  10. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
  11. Björn Þór Jónsson, Michael J. Franklin, Divesh Srivastava: Interaction of Query Evaluation and Buffer Management for Information Retrieval. SIGMOD Conference 1998: 118-129
  12. Prasad Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton: Caching Multidimensional Queries Using Chunks. SIGMOD Conference 1998: 259-270
  13. Jarek Gryz: Query Folding with Inclusion Dependencies. ICDE 1998: 126-133
  14. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
  15. Julie Basu, Arthur M. Keller, Meikel Pöss: Centralized versus Distributed Index Schemes in OODBMS - A Performance Analysis. ADBIS 1997: 162-169
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:11 2009