Reorganization of objects in an object databases is an important component
of several operations like compaction, clustering, and schema evolution. Th
e high availability requirements (24 x 7 operation) of certain application
domains requires reorganization to be performed on-line with minimal intere
ference to concurrently executing transactions.
In this paper, we address the problem of on-line reorganization in object d
atabases, where a set of objects have to be migrated from one location to a
nother. Specifically, we consider the case where objects in the database ma
y contain physical references to other objects. Relocating an object in thi
s 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 wi
th minimal interference to concurrently executing transactions. The IRA alg
orithm 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 r
esponse times of concurrently executing transactions and on overall system
throughput. We also describe how the IRA algorithm can handle system failur
es.