On-line reorganization in object databases

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 × 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 throughput. We also describe how the IRA algorithm can handle system failures.

REFERENCES

• AFG95: Laurent Amsaleg , Michael J. Franklin , Olivier Gruber, Efficient Incremental Garbage Collection for Client-Server Object Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.42-53, September 11-15, 1995
• AON96: Kiran J. Achyutuni , Edward Omiecinski , Shamkant B. Navathe, Two techniques for on-line index modification in shared nothing parallel databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.125-136, June 04-06, 1996, Montreal, Quebec, Canada
• ARS+97: Srinivas Ashwin , Prasan Roy , S. Seshadri , Abraham Silberschatz , S. Sudarshan, Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting, Proceedings of the 23rd International Conference on Very Large Data Bases, p.366-375, August 25-29, 1997
• BKKK87: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• BLR+97: Philip Bohannon , Daniel Lieuwen , Rajeev Rastogi , Avi Silberschatz , S. Seshadri , S. Sudarshan, The Architecture of the Dalí Main-Memory Storage Manager, Multimedia Tools and Applications, v.4 n.2, p.115-151, March 1997 [doi>10.1023/A:1009662214514 ]
• CWZ94: Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn, Partition selection policies in object database garbage collection, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.371-382, May 24-27, 1994, Minneapolis, Minnesota, United States
• Edi96: B. Salzberg (Special Issue Editor). Special issue on online reorganization. IEEE Data Engineering Bulletin, 19(2), June 1996.
• EGK95: André Eickler , Carsten Andreas Gerlhof , Donald Kossmann, A Performance Evaluation of OID Mapping Techniques, Proceedings of the 21th International Conference on Very Large Data Bases, p.18-29, September 11-15, 1995
• JLR+94: H. V. Jagadish , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Sudarshan, Dalí: A High Performance Main Memory Storage Manager, Proceedings of the 20th International Conference on Very Large Data Bases, p.48-59, September 12-15, 1994
• KW93: Elliot K. Kolodner , William E. Weihl, Atomic incremental garbage collection and recovery for a large stable heap, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.177-186, May 25-28, 1993, Washington, D.C., United States
• LRSS99: M.K. Lakhamraju, R. Rastogi, S. Seshadri, and S. Sudarshan. On-line reorganization of objects. In Technical Report, Bell-labs, February 1999.
• MN92: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• NOPH92: Scott Nettles , James O'Toole , David Pierce, Replication-Based Incremental Copying Collection, Proceedings of the International Workshop on Memory Management, p.357-364, September 17-19, 1992
• Omi96: E. Omiecinski. Concurrent file reorganization: Clustering, conversion and maintenance. IEEE Data Engineering Bulletin, 19(2), 1996.
• SC92a: V. Srinivasan , Michael J. Carey, Compensation-based on-line query processing, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.331-340, June 02-05, 1992, San Diego, California, United States
• SC92b: V. Srinivasan , Michael J. Carey, Performance of On-Line Index Construction Algorithms, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.293-309, March 23-27, 1992
• SD92: Betty Salzberg , Allyn Dimock, Principles of Transaction-Based On-Line Reorganization, Proceedings of the 18th International Conference on Very Large Data Bases, p.511-520, August 23-27, 1992
• TN91: Manolis M. Tsangaris , Jeffrey F. Naughton, A stochastic approach for clustering in object bases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.12-21, May 29-31, 1991, Denver, Colorado, United States
• WMK94: William J. McIver, Jr. , Roger King, Self-adaptive, on-line reclustering of complex object data, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.407-418, May 24-27, 1994, Minneapolis, Minnesota, United States
• YNY94: Voon-Fee Yong , Jeffrey F. Naughton , Jie-Bing Yu, Storage Reclamation and Reorganization in Client-Server Persistent Object Stores, Proceedings of the Tenth International Conference on Data Engineering, p.120-131, February 14-18, 1994
• ZS96a: Chendong Zou , Betty Salzberg, On-line reorganization of sparsely-populated B+-trees, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.115-124, June 04-06, 1996, Montreal, Quebec, Canada
• ZS96b: C. Zou and B. Salzberg. Towards efficient online database reorganization. IEEE Data Engineering Bulletin, 19(2):33-40, June 1996.
• ZS98: Chendong Zou , Betty Salzberg, Safely and Efficiently Updating References During On-line Reorganization, Proceedings of the 24rd International Conference on Very Large Data Bases, p.512-522, August 24-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Theory