Browse Prior Art Database

Object Location Algorithm

IP.com Disclosure Number: IPCOM000105989D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 61K

Publishing Venue

IBM

Related People

Calo, SB: AUTHOR [+3]

Abstract

An algorithm for quickly locating objects in an object-oriented database is disclosed.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Object Location Algorithm

      An algorithm for quickly locating objects in an object-oriented
database is disclosed.

      Assume that objects are organized as follows:  each object
belongs to only one class; and, classes may belong to other classes,
or have children that are classes.  It is also assumed that classes
are more than definitional.  Useful information is contained in
classes and there is a need to reference and retrieve information
from both classes and objects.

      Each class is assigned a two-byte class identifier.  It is
assumed that classes are far less numerous than objects.  Therefore,
the class identifier is obtained either by reusing the class
identifier of a previously deleted class that is sufficiently aged,
or by incrementing a two-byte counter and assigning the result as the
class identifier.

      An array of pointers is maintained to locate a class and to
locate a directory of objects in that class.  The class identifier is
used as an index into the array.  Each element of the array points to
a data structure that indicates the location of the class represented
by the class identifier and by a directory containing the locations
of all the objects in the class.

      Classes may be quickly accessed from the class identifier using
the array.  If the class name is supplied, then:

1.  The class name is hashed;
2.  The hash value is used to locate a hash queue entry (each hash
    queue entry contains a class name and class identifier);
3.  The hash queue entry is used to obtain the class identifier; and
4.  The class identifier is used to access the class or object
    directory.

      An object identifier is eight bytes long.  The Figure shows the
format of an object identifier.  The object identifier contains a
two- byte class identifier.  This class identifier is the identifier
of the class to which the object belongs.

      The four-byte hash value is obtained by a...