Fast determination of subtype relationship in a single inheritance type hierarchy

Claim 3

The method of claim 1, wherein the step of providing includes the step of performing Huffman coding on each one of the plurality of objects in the database.

Claim 4

The method of claim 1, wherein the step of providing includes the steps of: determining a maximum number of siblings for each level of the single inheritance type hierarchy; determining for each level of the single inheritance type hierarchy a minimum number of bits M L needed to uniquely number a maximum number of siblings for the respective level; adding together the minimum number of bits M L for each level in the single inheritance type hierarchy to obtain a value B, which equals a total number of bits necessary to uniquely identify each one of the plurality of objects in the database; assigning each one of the plurality of objects in database a value A N which has M L bits, wherein the value A N is unique for each one of the plurality of objects with respect to its siblings; concatenating the values A N for each one of the plurality of objects, with a left-most bit being a first digit of the value A N of a top level object, and successively next left-most bits that are concatenated being the remaining digits of the top level object followed by the values A N of each of an object's ancestors; and right-filling with 0's the concatenated values of A N until the concatenated values of A N with right-filled 0's has the total number of bits B to form the binary bit pattern for each one of said plurality of objects.

Claim 5

The method of claim 3, wherein, subsequent to determining M L and B, the step of providing further includes the step of forming said mask by filling left-most bits of a binary number B bits long with a number C of 1's and right-filling with 0's where C= ##EQU2## Q being the level L of an object having the mask that is being formed.

Claim 6

A computer programmed to identify a first object as an ancestral object of a second object said computer comprising: a database adapted to store a plurality of objects according to a single inheritance type hierarchy including a plurality of levels; means for providing each one of the plurality of objects in the database with a corresponding unique binary number, a binary bit pattern and a mask, each one of the binary patterns containing information which identifies ancestors of the corresponding object in the single inheritance type hierarchy, and the mask containing information as to how many bits in said binary bit pattern are significant; means for performing a bit-wise AND of the binary bit pattern of the first object with the mask of the second object to produce a result; and means for comparing said result with the binary pattern of the second object, a match indicating to said computer that the first object is either an instance of the second object or an ancestral object of said second object, and a nonmatch indicating the first object is neither an instance of the second object nor an ancestral object of the second object.

Claim 7

A computer programmed to identify a first object as an ancestral object of a second object said computer comprising: a database adapted to store a plurality of objects according to a single inheritance type hierarchy including a plurality of levels; means for providing each one of the plurality of objects in the database with a corresponding unique binary number, a binary bit pattern and a mask, each one of the binary patterns containing information which identifies ancestors of the corresponding object in the single inheritance type hierarchy, and the mask containing information as to how many bits in said binary bit pattern are significant; means for performing a bit-wise AND of the binary bit pattern of the first object with the mask of the second object to produce a result; and means for comparing said result with the binary pattern of the second object, a match indicating to said computer that the first object is either an instance of the second object or an ancestral object of said second object, and a nonmatch indicating the first object is neither an instance of the second object nor an ancestral object of the second object.

Claim 8

The computer of claim 5, wherein, the means for providing, the means for performing and the means for comparing are each implemented with a program written in a rule-based language.

Claim 9

The computer of claim 5, wherein the means for providing includes means for performing Huffman coding on each one of said plurality of objects in the single inheritance type hierarchy.

Claim 10

The computer of claim 5, wherein the means for providing includes: means for determining a maximum number of siblings for each level of the single inheritance type hierarchy; means for determining for each level of the single inheritance type hierarchy a minimum number of bits M L needed to uniquely number a maximum number of siblings for the respective level; means for adding together the minimum number of bits M L for each level in the single inheritance type hierarchy to obtain a value B, which equals a total number of bits necessary to uniquely identify each one of the plurality of objects in the database; means for assigning each one of the plurality of objects in the database a value A N which has M L bits, wherein the value A N is unique for each of said objects with respect to its siblings; means for concatenating the values A N for each one of the plurality of objects, with a left-most bit being a first digit of the value A N of a top level object, and successively next left-most bits that are concatenated being the remaining digits of the top level object followed by the values A N of each of an object's ancestors; and means for right-filling with 0's the concatenated values of A N until the concatenated values of A N with right-filled 0's has the total number of bits B to form the binary bit pattern for each one of the plurality of the objects.

Claim 11

The computer of claim 8, wherein the means for providing further includes means for forming said mask, subsequent to determining M L and B, by filling left-most bits of a binary number B bits long with a number C of 1's and right-filling with 0's, where C= ##EQU3## Q being the level L of an object having the mask that is being formed.