On-line Reorganization in Object Databases Mohana Krishna Lakhamraju, Rajeev Rastogi, S. Seshadri, and S. Sudarshan   View Paper (PDF)   Return to Research Sessions Abstract Reorganization of objects in an object databases is an important component of several operations like compaction, clustering, and schema evolution. The high availability requirements (24 x 7 operation) of certain application domains requires reorganization to be performed on-line with minimal interference to concurrently executing transactions. In this paper, we address the problem of on-line reorganization in object databases, where a set of objects have to be migrated from one location to another. Specifically, we consider the case where objects in the database may contain physical references to other objects. Relocating an object in this case involves finding the set of objects (parents) that refer to it, and modifying the references in each parent. We propose an algorithm called the Incremental Reorganization Algorithm (IRA) that achieves the above task with minimal interference to concurrently executing transactions. The IRA algorithm holds locks on at most two distinct objects at any point of time. We have implemented IRA on Brahma, a storage manager developed at IIT Bombay, and conducted an extensive performance study. Our experiments reveal that IRA makes on-line reorganization feasible, with very little impact on the response times of concurrently executing transactions and on overall system throughout. We also describe how the IRA algorithm can handle system failures. References Note: References link to DBLP on the Web. [AFG95] Laurent Amsaleg , Michael J. Franklin , Olivier Gruber : Efficient Incremental Garbage Collection for Client-Server Object Database Systems. VLDB 1995 : 42-53 [AON96] Kiran J. Achyutuni , Edward Omiecinski , Shamkant B. Navathe : Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases. SIGMOD Conf. 1996 : 125-136 [ARS+97] S. Ashwin , Prasan Roy , S. Seshadri , Abraham Silberschatz , S. Sudarshan : Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting. VLDB 1997 : 366-375 [BKKK87] Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth : Semantics and Implementation of Schema Evolution in Object-Oriented Databases. SIGMOD Conference 1987 : 311-322 [BLR+97] Philip Bohannon , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Seshadri , S. Sudarshan : The Architecture of the Dalí Main-Memory Storage Manager. Multimedia Tools and Applications 4(2) : 115-151(1997) [CWZ94] Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn : Partition Selection Policies in Object Database Garbage Collection. SIGMOD Conference 1994 : 371-382 [Edi96] Betty Salzberg : Letter from the Special Issue Editor. Data Engineering Bulletin 19(2) : 2-3(1996) [EGK95] André Eickler , Carsten Andreas Gerlhof , Donald Kossmann : A Performance Evaluation of OID Mapping Techniques. VLDB 1995 : 18-29 [JLR+94] H. V. Jagadish , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Sudarshan : Dalí: A High Performance Main Memory Storage Manager. VLDB 1994 : 48-59 [KW93] Elliot K. Kolodner , William E. Weihl : Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. SIGMOD Conference 1993 : 177-186 [LRSS99] ... [MN92] C. Mohan , Inderpal Narang : Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992 : 361-370 [NOPH92] Scott Nettles , James O'Toole , David Pierce : Replication-Based Incremental Copying Collection. IWMM 1992 : 357-364 [Omi96] Edward Omiecinski : Concurrent File Reorganization: Clustering, Conversion and Maintenance. Data Engineering Bulletin 19(2) : 25-32(1996) [SC92a] V. Srinivasan , Michael J. Carey : Compensation-Based On-Line Query Processing. SIGMOD Conference 1992 : 331-340 [SC92b] V. Srinivasan , Michael J. Carey : Performance of On-Line Index Construction Algorithms. EDBT 1992 : 293-309 [SD92] Betty Salzberg , Allyn Dimock : Principles of Transaction-Based On-Line Reorganization. VLDB 1992 : 511-520 [TN91] Manolis M. Tsangaris , Jeffrey F. Naughton : A Stochastic Approach for Clustering in Object Bases. SIGMOD Conference 1991 : 12-21 [WMK94] William J. McIver Jr. , Roger King : Self-Adaptive, On-Line Reclustering of Complex Object Data. SIGMOD Conference 1994 : 407-418 [YNY94] Voon-Fee Yong , Jeffrey F. Naughton , Jie-Bing Yu : Storage Reclamation and Reorganization in Client-Server Persistent Object Stores. ICDE 1994 : 120-131 [ZS96a] Chendong Zou , Betty Salzberg : On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conf. 1996 : 115-124 [ZS96b] Chendong Zou , Betty Salzberg : Towards Efficient Online Database Reorganization. Data Engineering Bulletin 19(2) : 33-40(1996) [ZS98] Chendong Zou , Betty Salzberg : Safely and Efficiently Updating References During On-line Reorganization. VLDB 1998 : 512-522 BIBTEX @inproceedings{DBLP:conf/sigmod/LakhamrajuRSS00,   author    = {Mohana Krishna Lakhamraju and                 Rajeev Rastogi and                 S. Seshadri and                 S. Sudarshan},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {On-line Reorganization in Object Databases},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {58-69},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.