Data retrieval system

• US 6,236,988 B1
• Filed: 09/03/1998
• Issued: 05/22/2001
• Est. Priority Date: 09/05/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aldred, Barry Keith
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/146,789
• Time in Patent Office: 992 Days
• Field of Search: 707/1, 707/3, 707/2, 707/4, 707/5, 707/6, 707/7, 707/100, 707/102, 707/103, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A data retrieval system in which a plurality of objects having a multi-level hierarchical relationship are stored is disclosed. Thus, each object has a respective parent and a set of children. The system includes an index table comprising a respective name and associated identifier for each object, and a data table comprising a respective set of attributes and a position key associated with each object in the system. Each position key comprises a series of components, each component corresponding to a level of the hierarchy. A first component of said key stores the identifier of an associated object, and each successive component stores the identifier of the parent of the object stored in the previous component.

Claims

1. A data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, comprising:

an index table comprising a name and associated identifier for each object; and

a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component.

2. The data retrieval system of claim 1 wherein said index table further comprises an attribute storing the level of each object in the system.

3. The data retrieval system of claim 1 wherein said index table comprises a position key associated with each object in the system, and said data table includes an identifier associated with each object and a respective identifier of the parent of each object in the system.

4. A method for retrieving an object name for an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object;

and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component, said method comprising the steps of;

specifying an object identifier for the object; and

retrieving from said index table the name for the object whose stored identifier matches said specified object identifier.

5. A method for retrieving the descendants of an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object;

and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component and wherein said index table further comprises an attribute storing the level of each object in the system, comprising the steps of;

specifying an object identifier for the object;

searching the index table to ascertain the hierarchical level of said object;

selecting from the data table objects for which the position key component for said level matches the object identifier;

identifying objects wherein the position key component for the first hierarchical level below said level are not null; and

retrieving the object identifiers for said identified objects.

6. The method of claim 5 wherein only the immediate children of said object are to be retrieved, wherein said identifying further comprises locating those objects for which the position key component for the first hierarchical level below said level are not null and the position key component for the next hierarchical level below said first hierarchical level are null;

and wherein said retrieving comprises retrieving the respective object identifiers for those located objects.

7. The method of claim 5 wherein said selecting, said identifying and said retrieving are carried out in a single traverse of said data table.

8. The method of claim 5 wherein the retrieved object identifiers are stored in each of the first components of the respective position keys.

9. A method for retrieving an object name for an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component, and wherein said index table comprises a position key associated with each object in the system, and said data table includes an identifier associated with each object and a respective identifier of the parent of each object in the system, said method comprising the steps of:

specifying an object identifier for the object; and

retrieving from said index table the name for the object whose stored identifier matches said specified object identifier.

10. A method for retrieving the immediate children of an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component, and wherein said index table comprises a position key associated with each object in the system, and said data table includes an identifier associated with each object and a respective identifier of the parent of each object in the system, said method comprising the steps of:

specifying an object identifier for the object; and

for objects where the contents of the parent identifier match the identifier of the object, retrieving the respective object identifiers.

11. A method for retrieving the descendants of an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object;

and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component and wherein said index table further comprises an attribute storing the level of each object in the system, comprising the steps of;

specifying an object identifier for the object;

ascertaining the hierarchical level of said object by determining if the first component of said position key matches said object identifier;

selecting from the data table objects for which the position key component for said level matches the object identifier;

identifying objects wherein the position key component for the first hierarchical level below said level are not null; and

retrieving the object identifiers for said identified objects.

12. A computer program product comprising computer readable program code stored on a computer readable recording medium, the program code including a relational database package including program code adapted to execute the method for retrieving the descendants of an object stored in a data retrieval system in which a plurality of objects related to each other in a multi-level hierarchy are stored, each object having a respective parent and a plurality of children, said system comprising an index table comprising a name and associated identifier for each object;

and a data table comprising a set of attributes and a position key for each object in the system, each position key comprising a plurality of components, each component corresponding to a level of said hierarchy, said position key comprising a first component comprising the identifier of an associated object and at least one successive component, each successive component storing the identifier of the parent of the object stored in the preceding component and wherein said index table further comprises an attribute storing the level of each object in the system, comprising the steps of;

specifying an object identifier for the object;

searching the index table to ascertain the hierarchical level of said object;

selecting from the data table objects for which the position key component for said level matches the object identifier;

identifying objects wherein the position key component for the first hierarchical level below said level are not null; and

retrieving the object identifiers for said identified objects.