Techniques of rewriting descendant and wildcard XPath using combination of SQL OR, UNION ALL, and XMLConcat() construct

• US 20070299834A1
• Filed: 06/23/2006
• Published: 12/27/2007
• Est. Priority Date: 06/23/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Liu, Zhen Hua, Krishnaprasad, Muralidhar, Chang, Hui Joe, Manikutty, Anand, Warner, James W., Arora, Vikas, Kotsovolos, Susan
• Granted Patent: US 7,730,080 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8365 Query optimisation

Abstract

A method for processing queries is provided. A first representation of a query is generated, where the query includes a certain operator that is to be performed based on an XPath expression that is expandable into multiple location paths. The first representation of the query is rewritten into a second representation that corresponds to an equivalent query, where rewriting the first representation includes expanding the XPath expression into the plurality of location paths and, based on the certain operator, including a plurality of operators in the second representation, where the plurality of operators include: a first set of operators that is to be performed based on each of the plurality of location paths, and a second set of operators that is to be performed based on data returned from at least one operator included in the first set of operators. The query may thereafter be executed based on the second representation. The second representation may be further rewritten to third representation depending on the physical storage of XML.

Claims

1. A method for processing queries, the method comprising the computer-implemented steps of:

generating a first representation of a certain query, wherein the certain query includes a certain operator to be performed based on an XML Path Language (XPath) expression, wherein the XPath expression indicates a plurality of location paths into which the XPath expression can be expanded; and

rewriting the first representation into a second representation that corresponds to an equivalent query of the certain query, wherein rewriting the first representation comprises;

expanding the XPath expression into the plurality of location paths; and

based on the certain operator, including a plurality of operators in the second representation, wherein the plurality of operators include;

a first set of operators to be performed based on each of the plurality of location paths, and

a second set of operators to be performed based on data to be returned from at least one operator included in the first set of operators.

2. The method of claim 1, further comprising executing the certain query based on the second representation, wherein executing the certain query includes evaluating one or more operators that are each included in any one of the first set of operators and the second set of operators.

3. The method of claim 1, further comprising:

based on the second representation, generating the equivalent query to include the plurality of operators; and

sending the equivalent query to a database server for execution.

4. The method of claim 1, wherein:

the XPath expression includes a descendant axis expression that indicates the plurality of location paths; and

the method further comprises determining the plurality of location paths from a schema based at least on the descendant axis expression.

5. The method of claim 4, wherein the schema is any one of an XML schema and a Document Type Definition (DTD).

6. The method of claim 4, wherein the descendant axis expression identifies nodes that descend from one of a root node and an element node of an XML document that is defined in the schema.

7. The method of claim 4, wherein:

the plurality of location paths include a first location path that is deterministic and a second location path that is recursive;

the first set of operators include;

first one or more operators to be performed based on the first location path, and

second one or more operators which, when evaluated, perform recursive XPath processing and evaluation based on the second location path; and

the second set of operators include at least one UNION ALL operator that is to be performed based on the data to be returned from the first one or more operators and the second one or more operators.

8. The method of claim 1, wherein:

the XPath expression includes a wildcard expression that indicates the plurality of location paths; and

the method further comprises determining the plurality of location paths from an XML schema based at least on the wildcard expression.

9. The method of claim 1, further comprising executing the query based on the second representation against storage structures in any one of a relational database and an object-relational database.

10. The method of claim 1, wherein the steps of the method are performed by one of a database server and an application server.

11. The method of claim 1, further comprising:

rewriting the second representation into a third representation that corresponds to a second equivalent query of the certain query, wherein rewriting the second representation comprises replacing at least one of the plurality of operators with one or more operators that reference one or more storage structures in one or more databases.

12. The method of claim 11, wherein the one or more storage structures are one or more relational tables that store data of XMLType as object-relational storage.

13. The method of claim 11, wherein the one or more storage structures are one or more relational tables that store data of XMLType as Large Object (LOB) storage.

14. The method of claim 11, wherein the one or more storage structures store one or more of any of path indices and value indices that index data of XMLType.

15. The method of claim 11, further comprising executing the certain query based on the third representation.

16. The method of claim 1, wherein:

the certain operator is an exists-node operator for determining the existence of nodes identified by the XPath expression;

the first set of operators includes a plurality of exists-node operators, wherein each of the plurality of exists-node operators is to be evaluated based on one of the plurality of location paths; and

the second set of operators includes at least one OR operator, wherein the at least one OR operator is to be evaluated based on results returned by each of the plurality of exists-node operators.

17. The method of claim 1, wherein:

the certain operator is an extract operator for retrieving XML fragments that are located at nodes identified by the XPath expression;

the first set of operators includes a plurality of extract operators, wherein each of the plurality of extract operators is to be evaluated based on one of the plurality of location paths; and

the second set of operators includes at least one XMLConcat operator, wherein the at least one XMLConcat operator is to be evaluated based on XML fragments returned by each of the plurality of extract operators.

18. The method of claim 1, wherein:

the certain operator is an XMLTable construct for storing a set XML fragments into a relational table, wherein each of the set of XML fragments is located at a node identified by the XPath expression;

the first set of operators includes a plurality of extract operators, wherein each of the plurality of extract operators is to be evaluated based on one of the plurality of location paths; and

the second set of operators includes;

an XMLConcat operator, wherein the XMLConcat operator is to be evaluated by concatenating XML fragments that are returned by each of the plurality of extract operators; and

at least one extract-value operator that is to be evaluated based on the content of one or more XML elements that are included in the concatenated XML fragments to be returned by the XMLConcat operator.

19. The method of claim 18, further comprising:

rewriting the second representation into a third representation that corresponds to a second equivalent query of the certain query, wherein rewriting the second representation comprises;

replacing the plurality of extract operators with a plurality of scalar subqueries, wherein each extract operator is replaced by a scalar subquery that is to be evaluated against a storage structure that stores the content of a single XML element identified by one of the plurality of location paths; and

in the second set of operators, replacing the XMLConcat operator with at least one UNION ALL operator, wherein the at least one UNION ALL operator is to be evaluated based on results returned by each of the plurality of scalar subqueries.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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