Garbage collection in object oriented databases using...

Details Garbage collection in object oriented databases using... Garbage collection in object oriented databases using...

1999-06-30

2002-03-26

Mizrahi, Diane D. (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06363403

ABSTRACT:

TECHNICAL FIELD
This invention relates to data processing systems and, more particularly, to memory reclamation in object oriented databases.
BACKGROUND OF THE INVENTION
There are al least two known approaches to memory reclamation, i.e., “garbage collection”, in data processing systems employing object oriented databases, namely, copying collector based, and mark and sweep based processes. The copying collector process traverses an entire object graph used in the system and copies so-called “live” objects into a new memory space and, then, the entire “old” memory space is reclaimed. In contrast the mark and sweep process marks all live objects by traversing the entire object graph and, then, traverses, i.e., sweeps, the entire database and deletes all objects that are not marked. With both of the above noted processes, the cost of traversing the entire object graph can be prohibitively expensive for databases larger than the memory size, particularly if there are many cross-page references.
One attempt at overcoming problems and limitations of prior known garbage collection processes is the use of a so-called “reference counting” process. Reference counting is based on the concept of keeping a count of the number of pointers pointing to an object. When the reference count of an object is zero, the object is defined as being garbage and eligible for collection. One such reference counting process is described in an article entitled “Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting”,
Proceedings of the International Conference on Very Large Databases,
Athens, Greece, August 1997, pages 366-375.
This prior reference counting process, however, relies on the assumptions that strict two phase locking (2PL) and strict write ahead logging (WAL) are employed, and that every strong pointer is followed to an object. Use of such assumptions caused significant inefficiencies in this prior known reference counting process.
SUMMARY OF THE INVENTION
Problems and limitations with prior known reference counting garbage collection processes are addressed in a reference counting process in which only the “last” detected strong pointer is followed to an object.
Moreover, no assumptions are made about the phase locking used in the transaction and strict WAL is not followed. Indeed, a relatively restricted local traversal of the object graph is employed which leads to higher efficiency.
Furthermore, in a client-server arrangement, updates made by a transaction running at the client may be reflected at the server after the transaction ends, and the updates are not required to be forced to the server before the end of the transaction.


REFERENCES:
patent: 4775932 (1988-10-01), Oxley et al.
patent: 5241673 (1993-08-01), Schelvis
patent: 5321834 (1994-06-01), Weiseret et al.
patent: 5398334 (1995-03-01), Topka et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 6199075 (2001-03-01), Ungar et al.
Practical distributed garbage collection for networks asynchronous clocks and message delay by Goug Kwan et al. (IEEE publication), in Paralel and Distributed Systems (Dec. 1994), pp. 406-411.*
Distributed/concurrent garbage collection in distributed memory systems by R. Kordale et al. (IEEE publication) in Object Orientation in Operating Systems (Dec. 1993), pp. 51-60.*
Incremental garbage collection in massive object storage by F. Brown (IEEE publication) in Computer Science Conference, (Feb. 2001) pp. 38-46.*
S. Ashwin et al., Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting, Proceedings of the 23rd VLDB Conference, Athens Greece, 1997, 10 pages.

Affiliated with

Also associated with

Rating

Garbage collection in object oriented databases using... does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2880058