Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-04-28
2004-02-24
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06697797
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to databases, and more particularly to address registers used by databases to control access to data contained within a database.
Databases typically belong to one of two major classes: object-oriented and relational. In an object-oriented database, an object typically consists of a unique object identifier (OID), coupled with a variable-sized block of bytes. In relational databases, data is typically stored in blocks of fixed sizes. Regardless of the type of database, it is a critical function of the database to keep track of the physical location in the storage medium of all data in the database. Both relational and object-oriented databases employ data block IDs to identify the blocks of data to be tracked. Databases generally track the physical location of data using one of two schemes: logical address registers (logical ID maps) and physical addresses.
Logical address registers use tuples to provide a one-to-one mapping between a logical address of a block of data and the physical address of that data. The database “refers” to the block of data by it's logical name, or “logical ID”, which is used to look up the physical address of that block of data in the logical address register.
Because the use of logical address registers must be persistent across database “opens” and “closes,” using such a register requires two accesses of the storage media. This is because retaining the logical address register in volatile memory makes the database much less robust, and because in order to avoid serious limitations on the number of data blocks a database can track, the logical address register must be permitted to grow larger than what can be stored in the volatile memory of typical hardware systems.
Accessing the storage media is one of the bottleneck functions of a database, especially on distributed databases. Logical operations, and accessing of data stored in volatile storage occur much more rapidly than accessing of data stored in stable storage media, such as on a hard drive.
Physical addresses as part of data blocks' IDs are therefore necessary for high-performance databases, in order to reduce the number of times the storage media must be accessed when a data block is referenced. Databases which use the physical address scheme for tracking data blocks use IDs which contain the actual physical address of the respective blocks (rather than the logical address), so that each reference to the block inherently contains the information necessary to physically locate the block on the storage media. In this way, the database can access the data block with only a single access of the storage media.
However, it is also necessary that a database be able to relocate blocks of data from one physical location on the storage media to another. For example, in object-oriented databases, the size of an object may outgrow the physical space available at its present location on the storage media. Also, a database's performance can be enhanced by strategic relocation of data blocks. For example, data blocks which are related to each other are preferably located together on the storage media so that they can be accessed as a group. Since each reference to a block of data within the database must be identified and the ID of the data must be amended to reflect the new location of the data block concurrently with the relocation of the data block, the nature of tracking physical addresses by including the physical address as part of the data block's ID makes movement of data blocks from one location on the storage media to another time consuming, and expensive in terms of consumption of hardware resources
Thus, there is a need for a database which employs a data tracking scheme which does not always require two accesses of the storage media in order to access a block of data, but which is able to relocate data blocks within the storage media more easily than is possible for databases relying on physical addresses as a part of the data block IDs.
SUMMARY OF THE INVENTION
In accordance with the present invention, a data tracking scheme for a database is provided which employs a “last-known location” register as a part of a data block's ID. In certain object-oriented databases embodying the present invention, for example, when an object is created, it is assigned a physical address, which is then included as an extension of the OID, and which is recorded in a logical address register. When the object is moved, rather than identifying every reference to the object within the database, only the physical address in the logical address register is updated. When a reference to the object is encountered during the operation of the database, the last-known-location extension of the OID is consulted for a valid last-known location, that is, a valid physical address. If such a valid last-known location exists, that physical location is accessed in order to retrieve the object. If the last-known-location extension of the OID contains an invalid last-known location, or if the physical address indicated contains something other than the desired object, the logical address register is accessed and the correct physical address is found. At this point, the reference to the object may (but need not) update the last-known address extension of the OID of the target object.
In another form of the invention, the database embodying to the present invention is a relational database. When a record in certain relational databases employing the data tracking scheme of the present invention includes a foreign key, for example, the record also includes a “hidden field”—that is, a field accessible only by the database engine—containing any last-known physical address of the record identified by the foreign key. When the database needs to access a record identified by a foreign key, the database attempts to locate the desired record without referring to the index of records containing the needed record by looking for a physical address in the hidden field, and, if it finds one, the database looks for the needed record at that address. If the hidden field does not contain a valid physical address, or if the physical address it contains is inaccurate, the database locates the needed record through the appropriate index, and the physical address in the hidden field can be updated.
One object of the present invention is to provide a database capable of accessing data blocks in fewer than two accesses of the storage media, which is also capable of tracking the relocation of a data block by amending the physical address in only a single reference to the relocated data block. Other objects and advantages of the present invention will be apparent from the following description.
REFERENCES:
patent: 5008786 (1991-04-01), Thatte
patent: 5369778 (1994-11-01), San Soucie et al.
patent: 5394534 (1995-02-01), Kulakowski et al.
patent: 5490258 (1996-02-01), Fenner
patent: 5611076 (1997-03-01), Durflinger et al.
patent: 5710920 (1998-01-01), Maruyama et al.
patent: 5713014 (1998-01-01), Durflinger et al.
patent: 5724575 (1998-03-01), Hoover et al.
patent: 5819282 (1998-10-01), Hooper et al.
patent: 5870763 (1999-02-01), Lomet
patent: 5893097 (1999-04-01), Hayata et al.
patent: 5909683 (1999-06-01), Miginiac et al.
patent: 5920869 (1999-07-01), Wakayama et al.
patent: 6003040 (1999-12-01), Mital et al.
patent: 6016497 (2000-01-01), Suver
patent: 6047284 (2000-04-01), Owens et al.
patent: 6085198 (2000-07-01), Skinner et al.
patent: 6148391 (2000-11-01), Petrick
patent: 6192370 (2001-02-01), Primsch
patent: 6535869 (2003-03-01), Housel, III
patent: 0 923 030 (1999-06-01), None
Object Data Management Group (ODMG 2.0) Book Extract, Rick Cattell, Mar. 1997.
Durflinger Kevin J.
Greer, Jr. Joseph E.
Harfmann Edmund R.
Hoggatt Dana L.
Logan Kim M.
Alam Shahid
Ly Anh
Micro Data Base Systems, Inc.
Woodard Emhardt Moriarty McNett & Henry LLP
LandOfFree
Method and apparatus for tracking data in a database,... 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 tracking data in a database,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for tracking data in a database,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293377