Indexing mechanism for efficient node-aware full-text search over XML

• US 8,219,563 B2
• Filed: 12/30/2008
• Issued: 07/10/2012
• Est. Priority Date: 12/30/2008
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Baby, Thomas, Liu, Zhen Hua, Lin, Wesley
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US12/346,327
• Publication Number:
  US 20100169354A1
• Time in Patent Office: 1,288 Days
• Field of Search: 707/797, 707/769, 707/765, 707/755, 707/756, 707/759, 707/741, 707/742, 707/711, 707999001-999003, 707/999.102
• US Class Current: 707/742
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

Techniques are provided for searching within a collection of XML documents. A relational table in an XML index stores an entry for each node of a set of nodes in the collection. Each entry of the relational table stores an order key and a path identifier along with the atomized value of the node. An index on the atomized value provides a mechanism to perform a node-aware full-text search. Instead of storing the atomized value in the table, a virtual column may be created to represent, for each node, the atomized value of the node. Alternately, each entry of the relational table stores an order key and a path identifier along with, for simple nodes, the atomized value, and for complex nodes, a null value. For a complex node with a descendant text node, a separate entry is stored for the descendant text node in the relational table.

Claims

1. A computer-implemented method comprising:

storing a table that stores data for a plurality of nodes in one or more XML documents,

the table comprising an entry for each node of the plurality of nodes, the entry for each node comprising;

path data that specifies a path, through the structure of the one or more XML documents, to the node; and

an atomized value of the node;

wherein the atomized value of at least one node comprises a first text value of the at least one node and a second text value of a descendant node of the at least one node;

wherein the at least one node comprises a first node name and the first text value, and wherein the descendant node comprises a second node name and the second text value;

wherein the atomized value of the descendant node comprises the second text value;

storing a full-text index of the atomized values stored in the entries of the table;

wherein the method is performed by one or more computing devices.

2. The computer-implemented method of claim 1, wherein said atomized value of the at least one node is formed, at least in part, by concatenating the first text value with the second text value.

3. The computer-implemented method of claim 1, wherein the atomized values are stored in a column of said table, said column being of a character large object type.

4. The computer-implemented method of claim 1, further comprising:

receiving a query that requires a text search of the one or more XML documents; and

rewriting said query to produce a rewritten query, wherein said rewritten query causes using said full-text index to compute said rewritten query.

5. The computer-implemented method of claim 1, further comprising:

receiving a query that specifies criteria, said criteria comprising;

one or more criteria for text contained in a node; and

one or more criteria for a path of a node;

rewriting said query to produce a rewritten query, wherein said rewritten query causes using full-text index and said table to compute which one or more nodes of said plurality of nodes satisfy said criteria.

10. The computer-implemented method of claim 1, wherein the descendant node is a first descendant node of the at least one node, wherein said atomized value of the at least one node is formed, at least in part, by concatenating the second text value of the first descendant node with a third text value of a second descendant node of the at least one node, wherein the second descendant node comprises a third node name and the third text value.

11. The computer-implemented method of claim 10, wherein the first descendant node and the second descendant node are adjacent descendant nodes of the at least one node, and wherein the atomized value for the at least one node comprises the second text value adjacent to the third text value.

6. A computer-implemented method comprising:

receiving a query that requests data from one or more XML documents;

wherein said one or more XML documents comprises a plurality of nodes;

evaluating the query using an index comprising a table that comprises a plurality of rows, each row of said plurality of rows corresponding to a node of said plurality of nodes;

wherein each row of said plurality of rows includes;

path data that specifies a path, through the structure of the one or more XML documents, to the corresponding node, and

an atomized value of the corresponding node, said atomized value represented in a virtual column of said table;

wherein the atomized value of at least one node comprises a first text value of a first descendant node of the at least one node and a second text value of a second descendant node of the at least one node;

wherein the first descendant node comprises a first node name and the first text value, and wherein the second descendant node comprises a second node name and the second text value;

wherein the atomized value of the first descendant node comprises the first text value;

wherein said certain index of said one or more XML documents comprises a full-text index, said virtual column being indexed by said full-text index;

wherein the method is performed by one or more computing devices.

7. The computer-implemented method of claim 6, wherein said atomized value of said virtual column is evaluated by concatenating the first text value with the second text value.

8. The computer-implemented method of claim 6, wherein the first text value and the second text value are obtained from said value column of said table.

9. The computer-implemented method of claim 6, further comprising:

rewriting said query to produce a rewritten query, wherein said rewritten query causes using said full-text index to compute said rewritten query.

12. The computer-implemented method of claim 6, wherein said atomized value of the at least one node further comprises a third text value of the at least one node.

13. The computer-implemented method of claim 6, wherein the first descendant node and the second descendant node are adjacent descendant nodes of the at least one node, and wherein the atomized value for the at least one node comprises the first text value adjacent to the second text value.

14. One or more non-transitory computer-readable storage media storing instructions which, when executed by one or more computing devices, cause:

storing a table that stores data for a plurality of nodes in one or more XML documents, the table comprising an entry for each node of the plurality of nodes, the entry for each node comprising;

path data that specifies a path, through the structure of the one or more XML documents, to the node; and

an atomized value of the node;

wherein the atomized value of at least one node comprises a first text value of the at least one node and a second text value of a descendant node of the at least one node;

wherein the at least one node comprises a first node name and the first text value, and wherein the descendant node comprises a second node name and the second text value;

wherein the atomized value of the descendant node comprises the second text value;

storing a full-text index of the atomized values stored in the entries of the table.

15. The one or more non-transitory computer-readable storage media of claim 14, wherein, when the instructions are executed by one or more computing devices, said atomized value of the at least one node is formed, at least in part, by concatenating the first text value with the second text value.

16. The one or more non-transitory computer-readable storage media of claim 14, wherein, when the instructions are executed by one or more computing devices, the atomized values are stored in a column of said table, said column being of a character large object type.

17. The one or more non-transitory computer-readable storage media of claim 14, wherein the instructions, when executed by one or more computing devices, further cause:

receiving a query that requires a text search of the one or more XML documents; and

rewriting said query to produce a rewritten query, wherein said rewritten query causes using said full-text index to compute said rewritten query.

18. The one or more non-transitory computer-readable storage media of claim 14, wherein the instructions, when executed by one or more computing devices, further cause:

receiving a query that specifies criteria, said criteria comprising;

one or more criteria for text contained in a node; and

one or more criteria for a path of a node;

rewriting said query to produce a rewritten query, wherein said rewritten query causes using full-text index and said table to compute which one or more nodes of said plurality of nodes satisfy said criteria.

19. The one or more non-transitory computer-readable storage media of claim 14, wherein the descendant node is a first descendant node of the at least one node, wherein, when the instructions are executed by one or more computing devices, said atomized value of the at least one node is formed, at least in part, by concatenating the second text value of the first descendant node with a third text value of a second descendant node of the at least one node, wherein the second descendant node comprises a third node name and the third text value.

20. The one or more non-transitory computer-readable storage media of claim 19, wherein the first descendant node and the second descendant node are adjacent descendant nodes of the at least one node, and wherein the atomized value for the at least one node comprises the second text value adjacent to the third text value.

21. One or more non-transitory computer-readable storage media storing instructions which, when executed by one or more computing devices, cause:

receiving a query that requests data from one or more XML documents;

wherein said one or more XML documents comprises a plurality of nodes;

evaluating the query using an index comprising a table that comprises a plurality of rows, each row of said plurality of rows corresponding to a node of said plurality of nodes;

wherein each row of said plurality of rows includes;

path data that specifies a path, through the structure of the one or more XML documents, to the corresponding node, and

an atomized value of the corresponding node, said atomized value represented in a virtual column of said table;

wherein the atomized value of at least one node comprises a first text value of a first descendant node of the at least one node and a second text value of a second descendant node of the at least one node;

wherein the first descendant node comprises a first node name and the first text value, and wherein the second descendant node comprises a second node name and the second text value;

wherein the atomized value of the first descendant node comprises the first text value;

wherein said certain index of said one or more XML documents comprises a full-text index, said virtual column being indexed by said full-text index.

22. The one or more non-transitory computer-readable storage media of claim 21, wherein, when the instructions are executed by one or more computing devices, said atomized value of said virtual column is evaluated by concatenating the first text value with the second text value.

23. The one or more non-transitory computer-readable storage media of claim 21, wherein, when the instructions are executed by one or more computing devices, the first text value and the second text value are obtained from said value column of said table.

24. The one or more non-transitory computer-readable storage media of claim 21, wherein the instructions, when executed by one or more computing devices, further cause:

rewriting said query to produce a rewritten query, wherein said rewritten query causes using said full-text index to compute said rewritten query.

25. The one or more non-transitory computer-readable storage media of claim 21, wherein said atomized value of the at least one node further comprises a third text value of the at least one node.

26. The one or more non-transitory computer-readable storage media of claim 21, wherein the first descendant node and the second descendant node are adjacent descendant nodes of the at least one node, and wherein the atomized value for the at least one node comprises the first text value adjacent to the second text value.