Accelerating value-based lookup of XML document in XQuery

• US 20090019077A1
• Filed: 07/13/2007
• Published: 01/15/2009
• Est. Priority Date: 07/13/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Tarachandani, Asha, Baby, Thomas, Chandrasekar, Sivasankaran, Agarwal, Nipun
• Granted Patent: US 7,836,098 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8373 Query execution

Abstract

A method and apparatus for accelerating value-based lookups of XML documents in XQuery is provided. XML indices can help to optimize SQL queries of XML documents stored in object-relational databases. Certain SQL/XML functions such as XMLTABLE( ) use XQuery expressions to query XML documents. Previously, such queries could not use the XML index because the PATH table of the XML index was not defined for XQuery semantics. Techniques described herein extend the XML index for use with queries that require evaluation of XQuery expressions. Consequently, techniques described herein accelerate value-based lookups of XML documents in XQuery by introducing the possibility of an index-assisted evaluation of XQuery expressions.

Claims

1. A method comprising performing a machine-executed operation involving instructions, wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform certain steps including:

for each particular node of a set of one or more nodes in an XML document, storing an entry for the particular node in a first index; and

for each complex node that is in the set of nodes and has one or more child nodes, performing steps comprising;

identifying a set of all simple nodes that are descendants of the complex node and that have no child nodes;

generating, based on the values of the simple nodes in the set, a representative node value for the complex node; and

associating the representative node value with an index entry in the first index for the particular complex node;

wherein the machine-executed operation is at least one of (a) sending said instructions over transmission media, (b) receiving said instructions over transmission media, (c) storing said instructions onto a machine-readable storage medium, or (d) executing the instructions.

2. The method of claim 1, further comprising:

for each simple node that has no child nodes, associating a node value with an index entry in the first index for the simple node.

3. The method of claim 1, wherein the identifying, generating, and associating steps are executed in response to receiving a query and by executing an operator contained within the query.

4. The method of claim 1, wherein the first index comprises a relational database table, and wherein the associating steps further comprise storing the node values and the representative node values in a column of values in the table.

5. The method of claim 3, further comprising:

receiving an expression that includes a target value; and

identifying, from the column of values, a matched value that is the same as the target value.

6. The method of claim 3, further comprising:

receiving a query, wherein the query has a path expression;

identifying a set of rows in the first index that are associated with one or more nodes to which the path expression refers; and

identifying, from the set of rows in the first index, one or more values of the one or more nodes to which the path expression refers.

7. The method of claim 5, wherein the path expression written in XQuery.

8. The method of claim 5, wherein the query comprises XQuery operators.

9. The method of claim 3, further comprising:

receiving a query comprising XQuery operators, wherein the query has a path expression in XQuery and a target value;

identifying a set of rows in the first index that are associated with one or more nodes to which the path expression refers;

identifying, from the set of rows, matched values that are the same as the target value;

identifying rows having the matched values; and

returning the nodes associated with the rows having the matched values.

10. The method of claim 8, wherein the query comprises a value-based lookup in XQuery.

11. The method of claim 1, further comprising:

storing the node values and the representative node values as keys in a second index, wherein each key is associated with one entry in the first index.

12. The method of claim 10, wherein the second index is a b-tree index.

13. The method of claim 10, further comprising:

receiving an expression that includes a target value; and

identifying, from the keys, a matched value that is the same as the target value.

14. The method of claim 10, further comprising:

receiving a query comprising XQuery operators, wherein the query has a path expression in XQuery and a target value;

identifying, from the keys, matched values that are the same as the target value;

identifying from the second index a set of entries associated with the matched values;

identifying, from the set of entries associated with the matched values, a subset of entries that are associated with one or more nodes to which the path expression refers; and

returning one or more nodes associated with the subset of entries.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

17. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

18. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

25. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

26. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

27. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

28. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

29. An apparatus for accelerating value-based lookups, comprising:

for each particular node of a set of one or more nodes in an XML document, means for storing an entry for the particular node in a first index;

for each simple node that has no child nodes, means for associating a node value with an index entry in the first index for the simple node; and

for each complex node that is in the set of nodes and has one or more child nodes, means for performing steps comprising;

means for identifying a set of all simple nodes that are descendants of the complex node and that have no child nodes;

means for generating, based on the values of the simple nodes in the set, a representative node value for the complex node; and

means for associating the representative node value with an index entry in the first index for the particular complex node.

30. The apparatus of claim 29, further comprising:

for each simple node that has no child nodes, means for associating a node value with an index entry in the first index for the simple node.