On-line reorganization in object-oriented databases

• US 6,343,296 B1
• Filed: 09/03/1999
• Issued: 01/29/2002
• Est. Priority Date: 09/03/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lakhamraju, Mohana Krishna, Rastogi, Rajeev, Sudarshan, Sundararajarao, Seshadri, Srinivasan
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/389,337
• Time in Patent Office: 879 Days
• Field of Search: 707/103, 707/104, 707/102, 707/101, 707/206, 707/8, 712/222
• US Class Current: 1/1
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

An on-line reorganization method of an object-oriented database with physical references involves a novel fuzzy traversal of the database, or a partition thereof, to identify the approximate parents of all migrating objects. Where the entire database is traversed the process begins from its persistent root. For traversals of a partition the process begins from each object with a reference pointing to it from outside the partition. To facilitate the identification of these inter-partitional objects an External Reference Table (“ERT”) is maintained. During the fuzzy traversal all new inserted and deleted references are tracked in a Temporary Reference Table (“TRT”). After the fuzzy traversal is completed, for each migrating object, a lock is obtained on the identified approximate parents and on all new parents in which references to the object were inserted, as indicated by the TRT. Based on the information in the TRT, locks are released on all approximate parents whose references to the object have been deleted. The references to the migrating object in the remaining set of locked parents are updated, the object is relocated and the locks are released. Alternatively, each parent of a migrating object can be individually locked, updated and released.

Claims

1. A method for on-line reorganization of at least a part of an object-oriented database containing physical references to one or more objects within said part of said database migrating from an old physical location to a new physical location, said method comprising the steps of:

performing a fuzzy traversal on said database without locking any objects other than to obtain a temporary latch of an object while a reference contained therein is read;

releasing said latch immediately after reading said reference in said object;

separately for each of said migrating objects, identifying during said fuzzy traversal all approximate parents of each of said migrating objects, each of said approximate parents being an object containing a reference to a migrating object;

identifying all objects to which a reference to one of said migrating objects is inserted or deleted by a transaction occurring on objects during said fuzzy traversal, each of said objects referred to respectively as an inserted parent and a deleted parent;

for each of said migrating objects, obtaining a write lock on each of its approximate parents;

for each of said migrating objects, obtaining a write lock on said inserted parents;

for each of said migrating objects, updating the reference to said migrating object found in each of said write locked objects;

for each of said migrating objects, relocating said migrating object to said new physical location; and

for each of said migrating objects, releasing each of said write locked objects.

2. The method of claim 1 wherein said sequence of steps of obtaining write locks on approximate parents, obtaining write locks on inserted parents, updating references, relocating said migrating object and releasing said write locks, is separately performed for one of said migrating objects at a time.

3. The method of claim 1 further comprising the step of maintaining a first list of approximate parents for each of said migrating objects.

4. The method of claim 1 wherein said part of said database is the entire database and said fuzzy traversal begins with a persistent root of said database.

5. The method of claim 1 wherein said part of said database is a first partition of a partitioned database, said first partition containing at least one migrating object, further comprising the step of maintaining an External Reference Table (“

ERT”

) for said first partition, said ERT of said first partition comprised of a list of objects having at least one parent from at least one other partition of said database, said parents referred to herein as inter-partitional parents, said fuzzy traversal is performed on said first partition beginning with each of said objects listed in said ERT of said first partition.

6. The method of claim 5 wherein said at least one of said objects listed on said ERT of said first partition is a migrating object, referred to herein as a root migrating object, further comprising the step of including among said approximate parents of said root migrating object said corresponding inter-partitional parents as indicated by said ERT.

7. The method of claim 1 wherein said part of said database is a first partition of a partitioned database, said first partition containing at least one migrating object, wherein said step of performing a fuzzy traversal of said first partition further comprising the step of identifying said objects of said partition from the object allocation information of said database and performing said fuzzy traversal on said identified objects.

8. The method of claim 1 further comprising the step of maintaining a Temporary Reference Table identifying each of said inserted parents and deleted parents, said Temporary Reference Table comprising at least one tuple, each of said tuples identifying one of said inserted parents or one of said deleted parents to a migrating object.

9. The method of claim 8 wherein said step of identifying all inserted references and deleted references of a migrating object continues until said step of releasing said write locked objects, further comprising following said step of updating, but before the step of releasing said write locked objects, the steps of:

determining whether any additional inserted parents or deleted parents of said migrating object were added to said Temporary Reference Table for which a write lock was not obtained;

obtaining a write lock on each of said inserted parents added to said Temporary Reference Table;

releasing said write locks on any object which contains a reference to a deleted parent;

updating said references in said inserted parents added to said Temporary Reference Table; and

repeating said determining, obtaining, releasing and updating steps of this claim 9 until no additional inserted parents and deleted parents for said migrating object are added to said Temporary Reference Table.

10. The method of claim 8 wherein said Temporary Reference Table is only maintained during said on-line reorganization of said part of said database.

11. The computer system of claim 10 wherein said database is partitioned into at least two partitions, further comprising a separate third data structure type for each of said partitions, said third data structure type referred to as an External Reference Table (“

ERT”

), said ERT of each of said partitions comprising a list of objects in said partition having at least one parent from another one of said partitions of said database, said parent referred to herein as an inter-partitional parent, wherein said software operating on said computer system includes instructions for independently performing said fuzzy traversal on each of said partitions, and instructions for said fuzzy traversal of one of said partitions to begin with each of said objects listed in said ERT of said traversed partition.

12. The method of claim 8 wherein said database is constrained by two-phase locking such that any active transaction involving an object prevents any other transaction on said action until said active transaction completes, further comprising the step of deleting from said Temporary Reference Table said identity of each of said deleted parents as the transaction which deleted said reference from said deleted parent, completes.

13. The method of claim 1 further comprising the steps of:

determining prior to said step of performing a fuzzy traversal whether there are any active transactions acting on said part of said database; and

waiting for said active transactions to complete before performing said fuzzy traversal.

14. The computer system of claim 13 further comprising software operating on said computer system for including said inter-partitional parents of an object listed on an ERT which is also a migrating object, among said approximate parents of said migrating object listed on said ERT.

15. The method of claim 1 wherein said database is not constrained by two phase locing, further comprising the steps of:

identifying each active transaction which results in a delete reference; and

stalling said fuzzy traversal at said object until said active transaction completes.

16. The method of claim 1 wherein one of said migrating objects has only one parent, said one parent being an inserted parent, further comprising the step of repeating said fuzzy traversal of said part of said database prior to said step of obtaining a write lock on each of said migrating object'"'"'s approximate parents.

17. A method for on-line reorganization of an object-oriented database containing physical references to one or more objects migrating from an old physical location to a new physical location, said method repeating the following steps separately for each of said migrating objects:

performing a fuzzy traversal on said database without locking any objects other than to obtain a temporary latch of an object while a reference contained therein is read,

releasing said latch immediately after reading said reference in said object;

separately for each of said migrating objects, identifying during said fuzzy traversal all approximate parents of each of said migrating objects, each of said approximate parents being an object containing a reference to a migrating object;

identifying all objects to which a reference to one of said migrating objects is inserted or deleted during said fuzzy traversal, each of said objects referred to respectively as an inserted parent and a deleted parent;

selecting one of said migrating objects;

obtaining a write lock on said migrating object;

obtaining a write lock on one of said approximate parents of said selected migrating object;

if said write locked approximate parent is not a deleted parent then updating the reference to said selected migrating object found in said write locked approximate parent;

releasing said write locked approximate parent;

repeating said obtaining, updating and releasing steps on said approximate parents until all references in each of said approximate parents of said migrating object has been updated, and said write lock o said approximate parents have been released;

obtaining a write lock on said inserted parents of said selected migrating object;

updating the reference to said selected migrating object found in said write locked inserted parent;

releasing said write lock on said updated inserted parent;

repeating said obtaining, updating and releasing steps on said inserted parents until all references in each of said inserted parents of said migrating object have been updated, and said write lock to said inserted parents have been released;

relocating said selected migrating object to said new physical location; and

releasing said write lock on said selected migrating object.

18. A computer implemented system for performing on-line reorganization of an object-oriented database containing physical references to one or more objects migrating from an old physical location to a new physical location, comprising:

software operating on said computer system for performing a fuzzy traversal on said database without locking any objects other than to obtain a temporary latch of an object while a reference contained therein is read;

a first data structure for maintaining a list of approximate parents corresponding to each of said migrating objects identified during said fuzzy traversal, each of said approximate parents being an object containing a reference to a migrating object;

a second data structure for maintaining a list of all inserted parents, deleted parents and the type of parent, whether inserted or deleted, corresponding to each of said migrating objects identified during said fuzzy traversal, wherein an inserted parent is an object to which a reference to one of said migrating objects is inserted and a deleted parent is an object from which a reference to one of said migrating objects is deleted;

software operating on said computer system for write locking said approximate parents;

software operating on said computer system for write locking said inserted parents and deleted parents;

software operating on said computer system for updating the references to said migrating objects which are found in said write locked approximate parents and inserted parents;

software operating on said computer system for releasing said write locks on said approximate parents and said inserted and deleted parents; and

software operating on said computer system for relocating said migrating object to said new physical location.