Semantic Data Caching and Replacement.

@inproceedings{DBLP:conf/vldb/DarFJST96,
  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, http://dblp.uni-trier.de}
}

Abstract

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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD 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/vldb8997 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/aDVD1 or /dvd

Printed Edition

Electronic Edition

• From CS Dept., University Trier (Germany)
  • Postscript file, via HTTP
  • Postscript file, via anonymous FTP
  • Postscript file, compressed by gzip, via anonymous FTP
  • Postscript file, compressed by compress, via anonymous FTP

References

[Bro92]

Kurt P. Brown: PRPL: A Database Workload Specification Language, v1.3. M.S. thesis, Univ. of Wisconsin-Madison 1992

[CDF+94]

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

[CFZ94]

Michael J. Carey, Michael J. Franklin, Markos Zaharioudakis: Fine-Grained Sharing in a Page Server OODBMS. SIGMOD Conference 1994: 359-370

[CKPS95]

Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200

[CKSV86]

George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221

[CR94]

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

[DFMV90]

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

[D+96]

...

[Fra96]

Michael J. Franklin: Client Data Caching: A Foundation for High Performance Object Oriented Database Systems. Kluwer 1996, ISBN 0-7923-9701-0

[FJK96]

Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160

[GR93]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents

[Jag90]

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342

[KB96]

Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)

[KK94]

Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438

[LMSS95]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104

[OTS94]

James O'Toole, Liuba Shrira: Hybrid Caching for Large-Scale Object Systems. POS 1994: 99-114

[RCK+95]

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)

[RK86]

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

[YL87]

H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254