Object-oriented database management systems are database management systems designed for applications with complex interrelated data and high performance requirements, such as computer aided design (CAD) and computer aided software engineering (CASE). Typically, object-oriented database management systems support object-oriented data models.
In an object-oriented data model, the data structures are encapsulated so that access to and manipulation of data is possible only through well-defined interfaces. The interfaces of an object-oriented data model include support for binary relations between objects. Such relations include, for example, one-to-many binary relations.
Previous implementations of one-to-many relations are based on the use of collection classes. A collection class is an object that stores an arbitrary number of addresses of other objects and allows iteration (or cursing) through those objects. Collection classes are generally implemented using discontiguous arrays of addresses. Management of these arrays requires storage allocation and freeing, as well as complex heuristics. With collection classes, unless special precautions are taken, multiple pointers to the same object will be accepted, thus giving multiple relationships, or worse yet, "halves" of a relationship, between the same two objects. The precautions needed to avoid repeated pointers are expensive in execution time, storage space, and/or complexity.
When a collection class is used in the implementation of a relation technology, it is generally embedded in schema classes. The collection class consumes storage both contiguously in the schema class itself and for the array, discontiguously outside the schema class. This relation technology is referred to as semi-sparse.
In current object-oriented database management systems and object-oriented data models, such as those using collection classes to implement relations, the one-to-many relations suffer from a number of performance and functional limitations. For example, a great deal of processing time is required in order to insert or remove relationships, and to iterate through the relationships. In addition, substantial amounts of storage are required. In many cases, most of the data in a data model comprises relationships, and thus, the amount of disk storage and main memory required for applications depends strongly on the efficiency with which relations can be represented in the data model. Thus, in current systems, system performance is degraded due to the requirement of a large amount of storage and inefficiency in implementing relations.
In addition to the above, in some object-oriented database management systems and data models, the functionality of the one-to-many relations may be limited. That is, some useful functions may be difficult, if not impossible, to provide. These functions include, for example, the ability to prevent the insertion of multiple relationships between the same two objects; the ability of cursors used to iterate through the relations to respond gracefully and predictably to interleaved insertion and/or removal of relationships and to the destruction of the relation fan being traversed; and the ability of cursors to traverse relation fans in both forward and backward directions and to dynamically reverse direction.
Thus, a need exists for a method of implementing relations and a method of implementing cursors which improves performance of the object-oriented database management system and object-oriented data model. A further need exists for a method of implementing relations wherein the information for the relations is stored contiguously within the related objects, thus eliminating the need for discontiguous storage. A yet further need exists for a relation implementation technique in which the amount of processing time and storage required for inserting relationships is decreased. Yet further, a need exists for a technique in which potential duplicate relationships can be detected. Further, a need exists for an iteration technique which allows cursor movement in both a forward and a backward direction and the ability to dynamically reverse the direction of the cursor.