Digital Symposium Collection 2000

The Persistent Cache: Improving OID Indexing in Temporal Object-Oriented Database Systems Kjetil Nørvåg   View Paper (PDF)   Return to Main-Memory Caching Abstract In a temporal OODB, an OID index (OIDX) is needed to map from OID to the physical location of the object. In a transaction time temporal OODB, the OIDX should also index the object versions. In this case, the index entries, which we call object descriptors (OD), also include the commit timestamp of the transaction that created the object version. The OIDX in a non-temporal OODB only needs to be updated when an object is created, but in a temporal OODB, the OIDX has to be updated every time an object is updated. This has previously been shown to be a potential bottleneck, and in this paper, we present the Persistent Cache (PCache), a novel approach which reduces the index update and lookup costs in temporal OODBs. We develop a cost model for the PCache, and use this to show that the use of a PCache can reduce the average access cost to only a fraction of the cost when not using the PCache. Even though the primary context of this paper is OID indexing in a temporal OODB, the PCache can also be applied to general secondary indexing, and can be especially beneficial for applications where updates are non-clustered. References Note: References link to DBLP on the Web. [1] Anupam Bhide , Asit Dan , Daniel M. Dias : A Simple Analysis of the LRU Buffer Policy and Its Relationship to Buffer Warm-Up Transient. ICDE 1993 : 125-133 [2] André Eickler , Carsten Andreas Gerlhof , Donald Kossmann : A Performance Evaluation of OID Mapping Techniques. VLDB 1995 : 18-29 [3] Ramez Elmasri , Gene T. J. Wuu , Vram Kouramajian : The Time Index and the Monotonic B+-tree. Temporal Databases 1993 : 433-456 [4] David B. Lomet , Betty Salzberg : Access Methods for Multiversion Data. SIGMOD Conference 1989 : 315-324 [5] ... [6] ... [7] Peter Muth , Patrick E. O'Neil , Achim Pick , Gerhard Weikum : Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method. VLDB 1998 : 452-463 [8] Kjetil Nørvåg , Kjell Bratbergsengen : Log-Only Temporal Object Storage. DEXA Workshop 1997 : 728-733 [9] Kjetil Nørvåg , Kjell Bratbergsengen : An Analytical Study of Object Identifier Indexing. DEXA 1998 : 38-49 [10] ... [11] ... [12] Takayuki Suzuki , Hiroyuki Kitagawa : Development and Performance Analysis of a Temporal Persistent Object Store POST/C++. Australian Database Conference 1996 : 1-10 [13-1] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1 Contents [13-2] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X Contents BIBTEX @inproceedings{DBLP:conf/vldb/Norvag99,   author    = {Kjetil N{\o}rv{\aa}g},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {The Persistent Cache: Improving OID Indexing in Temporal Object-Oriented                 Database Systems},    booktitle = {VLDB'99, Proceedings of 25th International Conference on Very                 Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {66-77},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM