Efficient query processing of XML data using XML index

• US 7,398,265 B2
• Filed: 09/16/2004
• Issued: 07/08/2008
• 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
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US10/944,170
• Publication Number:
  US 20050229158A1
• Time in Patent Office: 1,391 Days
• Field of Search: None
• 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/84 Mapping; Conversion
• CPC Class Codes: G06F 40/123 Storage facilities
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and apparatus is provided for translating queries, such as path expressions and SQL/XML constructs, into SQL statements to be executed against an XML index, which improves processor time as opposed to applying path expressions directly to the original XML documents to extract the desired information. Simple path expressions, filter expressions, descendant axes, wildcards, logical expressions, relational expressions, literals, and other path expressions are all translated into SQL for efficient querying of an XML index. Similarly, rules for translating SQL/XML constructs into SQL are provided.

Claims

1. A method for handling path-based queries, the method comprising:

receiving a path-based query that specifies a path associated with data in an XML document;

generating, based on the path, an index-enabled query that accesses an XML index that indexes a plurality of XML documents, including said XML document; and

executing the index-enabled query to use said XML index to retrieve said data required by the path-based query;

wherein generating the index-enabled query includes;

identifying a template, of a plurality of available templates, that corresponds to a format of a portion of the path-based query without regard to names of elements in the portion of the path-based query; and

generating at least a portion of the index-enabled query based on a rule associated with the template that corresponds to the format of the portion of the path-based query;

wherein each template, within the plurality of templates, corresponds to a different format of path expression;

wherein the rule associated with each template indicates how to translate path expressions that have the format, that corresponds to said each template, to expressions to be used in the index-enabled query.

2. The method of claim 1 wherein the steps of receiving, generating and executing are performed by a relational database server that manages access to the plurality of XML documents.

3. The method of claim 2 wherein:

generating the index-enabled query includes generating a SQL query; and

the step of executing the index-enabled query is performed by the relational database server executing the SQL query.

4. A machine-readable storage 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.

5. A machine-readable storage 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.

6. The method of claim 1 wherein:

the template is a first template of the plurality of templates;

the portion of the path-based query includes a subportion;

the step of generating the index-enabled query further includes identifying a second template, of the plurality of templates, that corresponds to the subportion of the path-based query; and

the portion of the index-enabled query that is based on the rule associated with the first template includes query content based on a rule associated with the second template.

7. A machine-readable storage 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.

8. The method of claim 1 wherein:

the portion of the path-based query is a simple path expression;

the step of identifying a template includes identifying a template for simple path expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for simple path expressions.

9. The method of claim 8 wherein generating at least a portion of the index-enable query based on the template for simple path expressions includes generating query content that selects from the index based on a pathid associated with the simple path expression.

10. A machine-readable storage 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.

11. A machine-readable storage 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.

12. The method of claim 1 wherein:

the portion of the path-based query is a filter expression;

the step of identifying a template includes identifying a template for filter expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for filter expressions.

13. A machine-readable storage 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.

14. The method of claim 1 wherein:

the portion of the path-based query is a descendant axes expression;

the step of identifying a template includes identifying a template for descendant axes expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for descendant axes expressions.

15. A machine-readable storage 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.

16. The method of claim 1 wherein:

the portion of the path-based query is a wildcard expression;

the step of identifying a template includes identifying a template for wildcard expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for wildcard expressions.

17. A machine-readable storage 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.

18. The method of claim 1 wherein:

the portion of the path-based query is a logical expression;

the step of identifying a template includes identifying a template for logical expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for logical expressions.

19. A machine-readable storage 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.

20. The method of claim 1 wherein:

the portion of the path-based query is a relational expression;

the step of identifying a template includes identifying a template for relational expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for relational expressions.

21. A machine-readable storage 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 20.

22. The method of claim 1 wherein:

the portion of the path-based query is a literal;

the step of identifying a template includes identifying a template for literals; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for literals.

23. A machine-readable storage 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 22.

24. The method of claim 1 wherein:

the portion of the path-based query is a cast expression;

the step of identifying a template includes identifying a template for cast expressions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for cast expressions.

25. A machine-readable storage 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 24.

26. The method of claim 1 wherein:

the portion of the path-based query is a text function;

the step of identifying a template includes identifying a template for text functions; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template for text functions.

27. A machine-readable storage 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 26.

28. The method of claim 1 wherein:

the portion of the path-based query includes an operator for determining whether a node in the XML document exists;

the step of identifying a template includes identifying a template associated with said operator; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template associated with said operator.

29. A machine-readable storage 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 28.

30. The method of claim 1 wherein:

the portion of the path-based query is a an operator for extracting a single value from the XML document;

the step of identifying a template includes identifying a template associated with said operator; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template associated with said operator.

31. A machine-readable storage 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 30.

32. The method of claim 1 wherein:

the portion of the path-based query is an operator for extracting one or more elements in the XML document;

the step of identifying a template includes identifying a template associated with the operator; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template associated with the operator.

33. A machine-readable storage 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 32.

34. The method of claim 1 wherein:

the portion of the path-based query is an operator for generating a collection of XML documents corresponding to root elements of an XML fragment;

the step of identifying a template includes identifying a template associated with said operator; and

the step of generating at least a portion of the index-enabled query based on a rule associated with the template includes generating at least a portion of the index-enable query based on the template associated with said operator.

35. A machine-readable storage 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 34.

36. The method of claim 1, wherein:

the XML index includes a path table;

each row in the path table corresponds to an indexed node in the XML document; and

each row indicates a value for the corresponding indexed node.

37. A machine-readable storage 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 36.

38. The method of claim 1, wherein:

the XML index includes a path table;

each row in the path table corresponds to an indexed node in the XML document; and

each row indicates a locator that is used to extract a fragment in the XML document that corresponds to the indexed node.

39. A machine-readable storage 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 38.

40. The method of claim 1, wherein:

the XML index includes a path table;

each row in the path table corresponds to an indexed node in the XML document; and

each row indicates a Dewey order key value that represents hierarchical order information, corresponding to the indexed node, relative to other nodes in the XML document.

41. A machine-readable storage 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 40.

42. A machine-readable storage 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.