Encoding method of members related by multiple concept or group hierarchies and identification of members in a corpus or a database that are descendants of one or more selected concepts or groups from the encoding

• US 5,940,822 A
• Filed: 08/29/1997
• Issued: 08/17/1999
• Est. Priority Date: 08/29/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Iyer, Balakrishna Raghavendra, Haderle, Donald J.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/921,197
• Time in Patent Office: 718 Days
• Field of Search: 707/2, 707/3, 707/4, 707/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method, apparatus, and article of manufacture for an encoder for encoding members in a concept hierarchy. A query is executed in a computer. The query is performed by the computer to retrieve data from a database stored on a data storage device connected to the computer. Members in the database that are related by one or more concept hierarchies are encoded. Then, members in one of the concept hierarchies that are descendants of one or more selected concepts are identified based on the encoding.

Claims

1. A method of executing a query in a computer, the query being performed by the computer to retrieve data from a database stored on a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies, wherein the encoding represents one or more concepts; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding by traversing each of the members related by the concept hierarchies only once.

2. The method of claim 1 above, wherein the step of encoding further comprises the steps of:

traversing each of the members in each of the concept hierarchies in postorder; and

assigning a label to each of the traversed members.

3. A method of executing a query in a computer, the query being performed by the computer to retrieve data from a database stored on a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder and assigning a label comprised of a non-negative integer to each of the traversed members; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

4. A method of executing a query in a computer, the query being performed by the computer to retrieve data from a database stored on a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder, assigning a label to each of the traversed members, assigning a combined code to each member of each hierarchy based on the assigned labels; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

5. The method of claim 4 above, wherein the step of identifying further comprises the step of using the combined code to identify members that are descendants of the selected concepts.

6. The method of claim 4 above, further comprising the steps of:

retrieving the combined code for a member; and

determining the assigned label for that member for one or more of the concept hierarchies using the combined code.

7. An apparatus for executing a query, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores a database;

one or more computer programs, performed by the computer, for encoding members in the database related by one or more concept hierarchies, wherein the encoding represents one or more concepts, and for identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding by traversing each of the members related by the concept hierarchies only once.

8. The apparatus of claim 7 above, wherein the means for encoding further comprises:

means for traversing each of the members in each of the concept hierarchies in postorder; and

means for assigning a label to each of the traversed members.

9. An apparatus for executing a query, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores a database;

one or more computer programs, performed by the computer, for encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder and assigning a label comprising a non-negative integer to each of the traversed members and for identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

10. An apparatus for executing a query, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores a database;

one or more computer programs, performed by the computer, for encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder, assigning a label to each of the traversed members, and assigning a combined code to each member of each hierarchy based on the assigned labels, and for identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

11. The apparatus of claim 10 above, wherein the means for identifying further comprises the means for using the combined code to identify members that are descendants of the selected concepts.

12. The apparatus of claim 10 above, further comprising:

means for retrieving the combined code for a member; and

means for determining the assigned label for that member for one or more of the concept hierarchies based on the combined code.

13. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for executing a query, the query being performed by the computer to retrieve data from a database stored in a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies, wherein the encoding represents one or more concepts; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding by traversing each of the members related by the concept hierarchies only once.

14. The method of claim 13 above, wherein the step of encoding further comprises the steps of:

traversing each of the members in each of the concept hierarchies in postorder; and

assigning a label to each of the traversed members.

15. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for executing a query, the query being performed by the computer to retrieve data from a database stored in a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder and assigning a label comprising a non-negative integer to each of the traversed members; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

16. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for executing a query, the query being performed by the computer to retrieve data from a database stored in a data storage device connected to the computer, the method comprising the steps of:

encoding members in the database related by one or more concept hierarchies by traversing each of the members in each of the concept hierarchies in postorder, assigning a label to each of the traversed members, and assigning a combined code to each member of each hierarchy based on the assigned labels; and

identifying members in one of the concept hierarchies that are descendants of one or more selected concepts based on the encoding.

17. The method of claim 16 above, wherein the step of identifying further comprises the step of using the combined code to identify members that are descendants of the selected concepts.

18. The method of claim 16 above, further comprising the steps of:

retrieving the combined code for a member; and

determining the assigned label for that member for one or more of the concept hierarchies using the combined code.