Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-03-24
2003-07-15
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S118000
Reexamination Certificate
active
06594751
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer systems and more particularly to pointer management in a database system using virtual memory mapping having a plurality of caches having persistent data.
BACKGROUND OF THE INVENTION
In object-oriented database systems, and any other systems having large numbers of inter-connected objects, inter-object references, sometimes called pointers, provide a complex structure providing access to the stored objects. Application programs, in accessing the object-oriented database, consume time by accessing and updating objects, following the intricate connections between objects, using both associative queries and direct traversal through the database, and performing some amount of computation as each object is visited.
Typical application areas for object-oriented databases are computer-aided design, manufacturing, and engineering, software development, electronic publishing, multimedia office automation, and geographical information systems. All of these application environments demand that an object-oriented database system be fast.
A typical object-oriented database system has a number of work stations or some other type of client computer connected through a server to the object-oriented database. Each client computer has its own cache memory in which data required by a client application program is placed.
Every object-oriented database system has some way to identify an object. Currently, some systems use an “object identifier” (OID), which embodies a reference to an object. Some systems use pointers. An operation called “dereferencing”, finds an object by following a pointer to the object and by making the object available to a requesting application.
Accessing data in the database involves copying the data into a cache memory of a client system. The cached data in some current systems is frequently discarded after the completion of a transaction because the pointers referencing the cached data become obsolete. Discarding the cached data insures consistency of data, but it increases communication between the client and the server computer. It also fails to make use of the principles of locality which encourage the use of a cache in the first place. Persistent data in the cache, however, requires a way to keep the data and the pointers referencing the data consistent with the database.
It remains desirable to have a way to update the data reference pointers in order to allow caching of persistent data in a form in which the dereferencing operation can be performed at high speed.
It is an object of the present invention to provide a method and apparatus for persistent caching of data in an object-oriented database system.
It is another object of the present invention to provide a method and apparatus having optimized pointer relocation for cached data.
It is another object of the present invention to provide a method and apparatus for optimized pointer relocation in virtual memory mapping architecture for an object-oriented database system.
SUMMARY OF THE INVENTION
The problems of pointer relocation optimization for persistent cached data are solved by the present invention of a method and apparatus for pointer relocation optimization for virtual memory mapping and transaction management in a database system.
There is provided an apparatus and a method for virtual memory mapping and transaction management for an object-oriented data base system having at least one permanent storage means for storing data and at least one data base, at least one cache memory for locally storing data addressed by physical addresses, and a processing unit including means for requesting data utilizing virtual addresses to access data in the cache memory, means for mapping virtual addresses to physical addresses and means for retaining the cached data after the conclusion of a transaction. Typically, the system has a plurality of client computers each having a cache memory, interconnected by a network, and each permanent storage means has a server computer. A single computer may serve as both a client computer and a server computer. The apparatus operates by relocating pointers to cached data in order to provide the client application with an efficient dereferencing operation. The apparatus further operates by maintaining the relocated pointers across a succession of transactions against the data held in the cache. The apparatus achieves its optimization benefits by reducing the frequency of pointer relocation maintenance operations to a minimum.
The relocation operations can be segregated into three categories: inbound relocation, forward relocation, and outbound relocation. Inbound relocation involves the translation of pointers on a page from their external format to a format and state usable by the client application. Inbound relocation occurs once for each occurrence of a database page entering the client cache. Forward relocation involves the translation of pointers on a page from a state, created by either inbound relocation or a previous forward relocation, that is no longer immediately usable by the client application to a state that is presently usable by the client application. Forward relocation of a particular page occurs at most once for each occurrence of a transaction in which the page is either read or modified, other than the first such transaction in which the page first enters the cache. Outbound relocation involves the translation of pointers from the form usable by the client application to their external form. Outbound relocation of a particular page occurs at the end of a successful transaction in which the page was modified, or when a modified page must otherwise be evicted from the cache. An advantage of the present invention is the management of address space used by the client application so as to decrease the number of forward relocations required across a succession of transactions.
REFERENCES:
patent: 5426747 (1995-06-01), Weinreb et al.
patent: 5509131 (1996-04-01), Smith et al.
patent: 5619723 (1997-04-01), Jones et al.
patent: 5649139 (1997-07-01), Weinreb et al.
patent: 5815415 (1998-09-01), Bentley et al.
patent: 5881379 (1999-03-01), Beier et al.
patent: 6073228 (2000-06-01), Holmqvist et al.
patent: 6094686 (2000-07-01), Sharma
patent: 6128717 (2000-10-01), Harrison et al.
“Generalized Scheme for Control Block Relocation”, IBM Technical Disclosure Bulletin, vol. 15, pp. 0980-2983, Feb. 1973.
Bataille Pierre-Michel
Chow Stephen Y.
Cohen Jerry
Kim Matthew
Perkins Smith & Cohen LLP
LandOfFree
Method and apparatus for pointer relocation optimization for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for pointer relocation optimization for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pointer relocation optimization for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3057217