Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-05
2004-04-27
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06728726
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer data storage systems, and more particularly to prefetching and caching objects from a data storage system.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright © 1998, 1999, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
The number of applications that use object-oriented techniques and languages continues to increase at a rapid pace. This growth in object-oriented applications has resulted in a corresponding growth in the use of object databases and repositories. Object databases and repositories provide for the persistent storage of object data in the same way that a conventional database provides for the storage of tables containing data. Object repositories and object-oriented databases are similar in that they both store data in an object format, however repositories in addition typically provide for the storage of metadata, that is, data about the object data, along with the object data. This metadata typically comprises information such as object formats and interfaces, object versions, check-in/check-out dates and personnel, database schemas, etc.
An object, as is known in the art, is a data structure that has a persistent state. The persistent state consists of attributes, which comprise scalar values and object references. A scalar value is a value such as a string, integer or boolean. An object reference specifies one side of a binary relationship between two objects that refer to each other. In other words, the reference is to another object, which in turn refers back to the referring object. Each attribute is identified by a name, and each attribute has a data type. The data type for an attribute identifies either the type of scalar value for the attribute or the type of relationship defined by the attribute.
In addition to attributes, the state of an object includes structures. A structure contains a group of attributes that are organized according to a particular data structure. This data structure can be a collection (also referred to as a set), sequence, array, table, or record structure. Each structure conforms to a named structure type, which defines the particular data structure (collection, sequence, array, etc.) and the types of attributes the structure can contain. Like any attribute, an attribute in a structure can be a scalar value or object reference. A structure that contains object references is called an object structure.
In addition to being part of the state of an object, a structure can exist independently of other objects. For example, a structure may contain a group of objects that is the result returned by a data storage system when it executes a query.
A persistent object can also have operations. The operations can be read and write operations that are generic, in that they apply to all types of objects, or that are customized, in that they apply only to particular objects or to particular types of objects. This invention applies to persistent objects with any kinds of operations, whether they are generic or customized.
Each object conforms to one or more types, where each type is identified by a name. An object type defines a set of attribute types and/or structure types that an object of the given type can contain.
An object is typically an instance of a class. A class is a body of code that implements one or more object types. The class includes code to produce new objects of each type that it implements and code to perform various operations on objects of types that it implements and on attributes and structures of such objects. The types of operations performed vary depending on the class, and generally include read and write operations for the attributes and structures of an object.
An object-oriented application generally accesses objects or collections of objects one at a time in a serial fashion. In addition, it tends to also retrieve a small data item on each of these accesses. For example, an application may iterate through a collection of objects, examining one or more attributes in each object of the collection. Alternatively, an application may examine a current object, and based on data in the object or on other factors, invoke an operation to cause the data storage system to retrieve another related object based on a relationship between the current object and the related object.
While object-oriented databases and repositories provide a consistent mechanism for object persistence, the serial manner in which object-oriented applications access objects in persistent storage can cause undesirable performance degradation. In a typical data storage system, each access to a data item incurs a relatively high fixed overhead to interface with the persistent storage, and a relatively low incremental cost to actually retrieve the desired data item. This access cost is compounded by the fact that a large number of accesses are typically required to obtain moderate amounts of data related to a particular object or grouping of objects.
Therefore, there is a need in the art for a mechanism to increase the performance of object-oriented systems. The mechanism should allow applications to access objects using current methods, while taking advantage of common patterns of use to decrease the time required to access objects.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
The systems and methods presented implement various strategies to prefetch relevant data items when an application first accesses an initial data item included in the state of an object. For the purposes of this application, prefetching means retrieving data for an object or related objects prior to an explicit request for access to the data by the application.
One such system for performing prefetches comprises a data storage system that provides persistent storage for object data comprising the state of the object. The data storage system uses an underlying physical storage system to actually store the data on a persistent storage unit. The physical storage system could be a hardware device, such as a disk, or a combination of hardware and software, such as a relational database system operating on a computer and disk. The data storage system includes software components that implement various strategies to prefetch data and store the data in a cache. The cache can be located in memory allocated to the data storage system, in memory allocated to an application using the data storage system to fetch object data, or in a physical storage system allocated to the data storage system. The data storage system or application to which the cache memory is allocated could be on a server system, a middle-tier system, or a client system.
In one method used to prefetch data, a data storage system provides access to an initial object whose state includes a structure that contains one or more other objects. The structure that contains those other objects is called the “structure context” of those other objects. The system creates a structure context description that “remembers” the objects in the structure and associates that structure context description with every object in the structure. When data for an attribute is fetched from one object in the structure (i.e. the object's structure context), data for the corresponding attribute is prefetched from the other objects in the structure, incurring a minimal incremental cost per item prefetched. The prefetched attribute data is held in a cache f
Bernstein Philip A.
Pal Shankar
Shutt David R.
Alam Shahid
Fleurantin Jean Bolte
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Prefetching and caching persistent objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prefetching and caching persistent objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefetching and caching persistent objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222541