Indexing and querying semi-structured documents

• US 20040128615A1
• Filed: 12/27/2002
• Published: 07/01/2004
• Est. Priority Date: 12/27/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Carmel, David, Kraus, Naama, Mandler, Benjamin
• Application Number:
  US10/331,454
• Publication Number:
  US 20040128615A1
• Time in Patent Office: Days
• US Class Current: 715/513
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

A method for indexing a semi-structured document, the method including arranging at least one structure entity of a semi-structured document into at least one node of a context structure tree, associating a unique context identifier with any of the structure entities, creating, for any value of any of the structure entities, a context-modified value by appending a context delimiter and the context identifier to the value, and inserting the context-modified value into a free-text tree.

Claims

1. A method for indexing a semi-structured document, the method comprising:

arranging at least one structure entity of a semi-structured document into at least one node of a context structure tree;

associating a unique context identifier with any of said structure entities;

for any value of any of said structure entities, creating a context-modified value by appending a context delimiter and said context identifier to said value; and

inserting said context-modified value into a free-text tree.

2. A method according to claim 1 and further comprising parsing said semi-structured document to identify any of said structure entities therein.

3. A method according to claim 1 wherein said associating step comprises associating a unique context identifier with any of said structure entities.

4. A method according to claim 1 wherein said inserting step comprises inserting either of said context delimiter and said context identifier as nodes in said free-text tree.

5. A method according to claim 4 and further comprising associating at least one link to said semi-structured document with any of said nodes in said free-text tree.

6. A method according to claim 1 and further comprising storing a data type of at least one of said structure entities in association with its corresponding node.

7. A method for querying semi-structured document indices, the method comprising:

traversing, in a context structure index, one or more context nodes corresponding to a context path of a query until a context node corresponding to a terminus of said context path is reached;

retrieving a context identifier of said context node;

appending a context delimiter followed by said context identifier to a value of said query, thereby forming a context-modified value;

traversing, in a free-text index, one or more text nodes corresponding to said context-modified value until said traversed text nodes form said context-modified value; and

retrieving any links associated with any of said text nodes corresponding to either of said context delimiter and said context identifier node, thereby forming results of said query.

8. A method according to claim 7 and further comprising retrieving a data type of said context node, and wherein said retrieving links step comprises retrieving where said value satisfies a data type operation specified in said query.

9. A method for querying semi-structured document indices, the method comprising:

appending a context delimiter followed to a value of a query, thereby forming a context-modified value;

traversing, in a free-text index, one or more text nodes corresponding to said context-modified value until said traversed text nodes form said context-modified value; and

retrieving any links associated with any of said text nodes corresponding to said context delimiter, thereby forming results of said query.

10. A method according to claim 9 wherein said retrieving step additionally comprises retrieving any links associated with any text nodes descending from said text node corresponding to said context delimiter, thereby forming results of said query.

11. A method for querying semi-structured document indices, the method comprising:

traversing, in a context structure index, one or more context nodes corresponding to a context path of a query until a context node corresponding to a terminus of said context path is reached;

retrieving a context identifier of said context node;

traversing, in a free-text index, one or more text nodes corresponding to a value of said query, wherein said value is of a context-specific wildcard query construct, until said traversed text nodes form said value; and

retrieving any links associated with any text nodes of said free-text index that descend from the terminus of said traversed value and that are at the desired context identifier, thereby forming results of said query.

12. Apparatus for indexing a semi-structured document, comprising:

a context structure tree comprising at least one node corresponding to at least one structure entity of a semi-structured document and a unique context identifier associated with said structure entity;

a context-modified value comprising a value of said structure entity, a context delimiter, and said context identifier; and

a free-text tree into which said context-modified value is inserted.

13. A system for indexing a semi-structured document, the system comprising:

means for arranging at least one structure entity of a semi-structured document into at least one node of a context structure tree;

means for associating a unique context identifier with any of said structure entities;

means for creating a context-modified value for any value of any of said structure entities by appending a context delimiter and said context identifier to said value; and

means for inserting said context-modified value into a free-text tree.

14. A system according to claim 13 and further comprising means for parsing said semi-structured document to identify any of said structure entities therein.

15. A system according to claim 13 wherein said means for associating is operative to associate a unique context identifier with any of said structure entities.

16. A system according to claim 13 wherein said means for inserting is operative to insert either of said context delimiter and said context identifier as nodes in said free-text tree.

17. A system according to claim 16 and further comprising means for associating at least one link to said semi-structured document with any of said nodes in said free-text tree.

18. A system according to claim 13 and further comprising means for storing a data type of at least one of said structure entities in association with its corresponding node.

19. A system for querying semi-structured document indices, the system comprising:

means for traversing, in a context structure index, one or more context nodes corresponding to a context path of a query until a context node corresponding to a terminus of said context path is reached;

means for retrieving a context identifier of said context node;

means for appending a context delimiter followed by said context identifier to a value of said query, thereby forming a context-modified value;

means for traversing, in a free-text index, one or more text nodes corresponding to said context-modified value until said traversed text nodes form said context-modified value; and

means for retrieving any links associated with any of said text nodes corresponding to either of said context delimiter and said context identifier node, thereby forming results of said query.

20. A system according to claim 19 and further comprising means for retrieving a data type of said context node, and wherein said means for retrieving links is operative to retrieve where said value satisfies a data type operation specified in said query.

21. A system for querying semi-structured document indices, the system comprising:

means for appending a context delimiter followed to a value of a query, thereby forming a context-modified value;

means for traversing, in a free-text index, one or more text nodes corresponding to said context-modified value until said traversed text nodes form said context-modified value; and

means for retrieving any links associated with any of said text nodes corresponding to said context delimiter, thereby forming results of said query.

22. A system according to claim 21 wherein said means for retrieving is additionally operative to retrieving any links associated with any text nodes descending from said text node corresponding to said context delimiter, thereby forming results of said query.

23. A system for querying semi-structured document indices, the system comprising:

means for traversing, in a context structure index, one or more context nodes corresponding to a context path of a query until a context node corresponding to a terminus of said context path is reached;

means for retrieving a context identifier of said context node;

means for traversing, in a free-text index, one or more text nodes corresponding to a value of said query, wherein said value is of a context-specific wildcard query construct, until said traversed text nodes form said value; and

means for retrieving any links associated with any text nodes of said free-text index that descend from the terminus of said traversed value and that are at the desired context identifier, thereby forming results of said query.

24. A computer program embodied on a computer-readable medium, the computer program comprising:

a first code segment operative to arrange at least one structure entity of a semi-structured document into at least one node of a context structure tree;

a second code segment operative to associate a unique context identifier with any of said structure entities;

a third code segment operative to create a context-modified value for any value of any of said structure entities by appending a context delimiter and said context identifier to said value; and

a fourth code segment operative to insert said context-modified value into a free-text tree.