On-line reorganization in object-oriented databases

Details On-line reorganization in object-oriented databases On-line reorganization in object-oriented databases

1999-09-03

2002-01-29

Coby, Frantz (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C712S222000

Reexamination Certificate

active

06343296

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to reorganization in object oriented databases. More specifically the present invention relates to a method for updating physical references to objects without interfering with executing applications.
BACKGROUND OF THE INVENTION
In an object oriented database data records, referred to as objects include reference pointers to other objects. In some systems these pointers are physical references, while other systems use logical references. A physical reference is an actual location, or address on a storage medium, where the referred to objects can be found. Logical references are object identifiers, unique for that object and independent of the physical location of the record.
By analogy, the address of a residence is a physical reference to an individual residing there. As long as the individual remains at that address, anyone visiting that address will find him. However, the same individual may move and no longer be associated with that address, in which case the address will exist, but the individual will not be found. Indeed, another individual may reside there.
In contrast, a social security number is a logical reference to an individual. No one else will receive the same number and the individual number, under ordinary circumstances will not change. However, the social security number alone does not indicate where to physically find the individual.
Since objects in an object oriented database are interrelated through references, it is necessary to traverse one or more and often many, intermediate objects, before reaching a particular object. If any of the intermediate objects cannot be reached then all subsequent objects will be unreachable. Thus it is imperative to keep track of all object migration, i.e., all physical relocations of an object.
The process of relocating, or migrating objects and updating the references to them, whether the references are physical or logical, is referred to as reorganization. Reorganization of objects in an object-oriented database is well known in the art and is an important component of several utilities like compaction, clustering, partitioning and schema evolution.
Compaction reduces fragmentation of various length objects, resulting from continuous allocation and de-allocation of space for these objects, by migrating objects to different locations and packing them closely. Clustering involves locating related objects within the same disk block or adjacent blocks. As a result the performance of transactions which access those sets of objects within a small time frame, is improved. In contrast to clustering, partitioning separates objects across several disks to enable concurrently accessed objects to be retrieved in parallel. Clustering and partitioning of objects is determined based on changes in workload and updates to objects. Schema evolution often requires objects to be moved since an object may not fit in its current location due to a size change caused by schema evolution.
When physical references are used each reference to an object, which may be many, must be updated whenever the object is physically relocated. For example, one prior art method of updating an object-oriented database with physical references maintains back pointers from every object in the database. In this manner, before an object is relocated, the back pointer enables quick and easy updating of the reference to the migrating object. However, maintaining back pointers greatly increases storage overheads and causes lock contention in back pointer lists of “popular” objects, which are pointed to from many parent objects. Thus, maintaining back pointers is unacceptable in many applications.
Logical references on the other hand, do not require updating since the logical reference is independent of the physical location of the object. However, the data record itself is not found merely from the logical reference. Rather a mapping procedure is executed to return the physical location of an object. It is only the one cross reference in the map that requires updating when an object is moved from one physical location to another.
Clearly, updating one cross reference in a map is more desirable than determining every physical reference to a relocated object. Indeed, where the cost of reorganization is of concern, one solution found in the prior art is to use logical references. However, while logical references require only one update for each relocated object, they entail one extra level of indirection for every access of the object, i.e. mapping. In a memory resident database, this increases the access path length to an object by a factor of two, and may also considerably increase main-memory requirements. These overheads are unacceptable in a number of scenarios such as call setup in telecommunications, which require response times to be in the order of hundreds of microseconds.
Even where the cost of physical references is acceptable over logical references, another issue must be addressed: that of concurrent transactions. The concern is that between the actual migration of an object and updating all physical references, an application that has been running may have retrieved the old reference. In other words, assume an object O points to location X for object O′ and O′ is relocated to location Y. While the pointer from
0
will be updated to point to Y, the concern is that immediately prior to updating the pointer at O, an application will have already retrieved the old pointer, stored it in its local memory and will follow the pointer to X, looking for O′.
One approach to this problem is to access the local memory of the application and actually change the physical reference whenever the referred to object has moved to another location. This requires an action-quiescent state during which all objects in the memory of active transactions and persistent roots are copied into a new space. This method, however, works only when the database manager has low level support from the hardware and operating systems including access to the local memory of the application. For example, the system must be able to change references in the registers and stacks of active transactions and trap certain pointer references using memory protection. Often times this is not available. For example, windows based systems do not allow access to this low level memory. In addition, those techniques use forwarding addresses which may require an extra I/O and require use of a complicated failure recovery technique to ensure consistency of the disk version of the database. See E. K. Kolodner and W. E. Weihl, “
Atomic Incremental Garbage Collection and Recovery of a Large Stable Heap,”
In Proceedings of ACM SIGMOD International Conference on Management of Data, pages 177-186, (Washington, D.C., May 1993), hereby incorporated by reference as if fully set forth herein.
Another approach is to find the set of parent objects with a reference to a migrating object O, lock them so they are unavailable to the application and update the reference in each parent object. The transaction locks the object, either with a read lock, thereby preventing any other application from reading the object, or with a write lock, allowing reading, but preventing any deletion or insertion of a reference contained within the object. Once a transaction has locked an object (in the appropriate mode), it can i) copy into its local memory any reference from that object to another; ii) delete a reference from that reference to another; and iii) copy a reference stored in its local memory into that object, so that the object now points to another object. In all of the above, the transaction is not required to hold a lock on the object to which the reference points.
Traditionally, the application effecting the migration of an object will lock out all transactions from the entire database. This is referred to as off-line reorganization. Finding the parents of O with off-line reorganization is accomplished by traversing an object graph of the databas

Affiliated with

Also associated with

Rating

On-line reorganization in object-oriented databases does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with On-line reorganization in object-oriented databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-line reorganization in object-oriented databases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2850258