Mechanism for efficiently evaluating operator trees

• US 20050228768A1
• Filed: 09/16/2004
• Published: 10/13/2005
• Est. Priority Date: 04/09/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Sedlar, Eric, Thusoo, Ashish, Chandrasekar, Sivasankaran, Murthy, Ravi, Agarwal, Nipun
• Granted Patent: US 7,603,347 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An XPath expression is converted into a tree-based representation where each node represents an operation to be performed and the links between nodes in the tree represent the flow of data between operations. The conversion may involve creating a parse tree for the XPath expression, and then converting the parse tree into an operator tree. The operator tree is constructed in such a way that execution of the XPath expression begins at the leaf nodes of the operator tree, and the results are then passed up the tree. After each node is executed, the results are either (1) passed to a filter that filters the results with a predicate statement or (2) passed to another node to be operated upon. This occurs until no nodes remain to be executed.

Claims

1. A method for processing XPath expressions, comprising the steps of:

receiving an XPath expression;

generating, based on said XPath expression, a tree-based representation of the XPath expression;

wherein the tree-based representation comprises nodes and links;

wherein the nodes of the tree-based representation represent operations to be performed; and

wherein the links between the nodes represent flow of data between operations.

2. The method of claim 1 wherein the step of generating a tree-based representation includes:

creating a parse tree for the XPath expression, and

converting the parse tree into an operator tree.

3. The method of claim 2 wherein the step of generating a tree-based representation further comprises the step of normalizing the parse tree by converting one or more reverse axes to forward axes.

4. The method of claim 2 wherein:

the XPath expression includes a location step; and

operator has, on its right hand side, an operator tree corresponding to the relation predicate.

5. The method of claim 1 further comprising, based on the tree-based representation, executing an operation associated with the XPath expression.

6. The method of claim 5 wherein the step of executing includes:

beginning at leaf nodes of the tree-based representation, performing operations associated with the leaf nodes; and

passing results of operations up to parent nodes of the nodes that performed the operations.

7. The method of claim 5 wherein the step of passing results includes:

if the parent of a node associated with an operation is a filter, then passing results of the operation to filter, wherein the filter filters the results with a predicate statement; and

if the parent of a node associated with an operation is an operator node, then passing results of the operation to the parent and executing the operation associated with the parent on said results.

8. The method of claim 1 wherein:

the XPath expression is associated with a requested operation; and

the method further comprises generating database commands, based on the tree-based representation, which, when executed, cause a database server to perform the requested operation.

9. The method of claim 8 wherein the step of generating database command includes generating commands that access an XML Index to perform the requested operation.

10. The method of claim 1 wherein:

the XPath expression is associated with a requested operation; and

the method further comprises

determining whether a database command can be generated, based on the tree-based representation, which, when executed, causes a database server to perform the requested operation; and

if a database command cannot be generated, then functionally evaluating operators in the tree-based representation to perform the requested operation.

11. 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.

12. 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.

13. 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.

14. 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.

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 5.

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 6.

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 7.

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 8.

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 9.

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 10.