EFFICIENT STREAMING EVALUATION OF XPATHS ON BINARY-ENCODED XML SCHEMA-BASED DOCUMENTS

• US 20090150412A1
• Filed: 12/05/2007
• Published: 06/11/2009
• Est. Priority Date: 12/05/2007
• Status: Active Grant

• Current Assignee: Oracle Corporation, Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Idicula, Sam, Chandrasekar, Sivasankaran, Agarwal, Nipun
• Granted Patent: US 9,842,090 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/8373 Query execution
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/146 Coding or compression of tree-structured data

Abstract

A database system may utilize XML schema information to increase the efficiency of an XPath streaming evaluation. The database system may access XML schema or translation information during the evaluation of an element, attribute, or value in an XML data source. Based on the XML schema or translation information, the database system may determine matches to an XPath expression without decoding any binary-encoded data in the XML data source. Also, based on the XML schema information, the database may selectively skip or evaluate portions of the XML data source depending on whether those portions are defined in the XML schema so as to possibly contain a match to one or more unmatched steps in the XPath expression. XML schema information may be compiled into a compiled representation of the XPath expression for additional efficiencies.

Claims

1. A computer-implemented method comprising the steps of:

encoding an XML data source, thereby forming an encoded XML data source,

wherein the XML data source comprises a textual representation of an element;

wherein the encoded XML data source comprises an encoded representation of the element;

receiving an XPath expression to be performed on the XML data source,

wherein the XPath expression comprises a textual reference to the element;

compiling the XPath expression, thereby forming a compiled XPath expression,

wherein the step of compiling comprises translating the textual reference into an encoded reference;

wherein the encoded reference is identical to the encoded representation; and

evaluating the compiled XPath expression on the encoded XML data source without decoding the encoded XML data source;

generating a result based on the evaluation.

2. The method of claim 1, wherein evaluating the compiled XPath expression comprises:

parsing the encoded representation of the element from an XML input stream carrying the encoded XML data source; and

comparing the encoded representation of the element to the encoded reference.

3. The method of claim 1 wherein the step of encoding the XML data source and the step of translating the textual reference into an encoded reference both comprise accessing translation information in a database, wherein the translation information maps textual information to encoded information.

4. The method of claim 1, wherein the XML data source is defined by an XML schema, wherein the step of encoding the XML data source and the step of translating the textual reference into an encoded reference both rely on a same algorithm applied to the XML schema.

5. The method of claim 1 wherein the encoded representation is an integer.

6. A computer-implemented method comprising the steps of:

receiving an XPath expression to be evaluated on a streamed XML data source, wherein the streamed XML data source is defined by an XML schema;

compiling the XPath expression, thereby forming a compiled XPath expression,

wherein the compiled XPath expression comprises a compiled representation of a step from the XPath expression;

wherein the compiled XPath expression also comprises parsing instructions associated with the compiled representation of the step;

wherein compiling the XPath expression comprises generating the parsing instructions based at least upon the XML schema and the step;

evaluating the compiled XPath expression on the streamed XML data source,

wherein, based on the parsing instructions, a portion of the streamed XML data source is not parsed;

generating a result based on the evaluation of the XPath expression.

7. The method of claim 6 wherein generating the parsing instructions comprises determining that a portion of the XML schema cannot define an element, attribute, or data value that matches a next step.

8. The method of claim 6, wherein generating the parsing instructions comprises determining that a portion of the XML schema defines an element, attribute, or data value that potentially matches a next step.

9. The method of claim 6 wherein the parsing instructions are to skip a particular number of characters or bytes in the streamed XML data source, wherein the particular number of characters or bytes is calculated from the XML schema.

10. The method of claim 6 wherein the parsing instructions are to skip a particular number of elements in the streamed XML data source, wherein the particular number of elements is calculated from the XML schema.

11. The method of claim 6 wherein the parsing instructions are to jump to a pointer for a particular element in the streamed XML data source, wherein the particular element is determined from the XML schema.

12. The method of claim 6 wherein the parsing instructions are to terminate evaluation of the streamed XML data source.

13. The method of claim 6 wherein the streamed XML data source is binary-encoded, and wherein the compiled representation of the step is also binary-encoded.

14. The method of claim 6 wherein evaluating the compiled XPath expression comprises sending the parsing instructions to an XML parser.

15. The method of claim 6 wherein the XPath expression comprises a second step, wherein compiling the compiled XPath expression comprises determining, based on the XML Schema, not to generate a compiled representation of the second step.

16. The method of claim 6, wherein the step indicates that it is to be matched to an element of a particular name, and wherein the compiled representation of the step does not include information indicating any name.

17. The method of claim 6 wherein the compiled XPath expression is a state machine.

18. A computer-implemented method comprising the steps of:

receiving an XPath expression to be evaluated on a streamed XML data source, wherein the streamed XML data source is defined by an XML schema;

while evaluating the XPath expression on the streamed XML data source,

based at least upon information derived from the XML schema, identifying a next portion of unevaluated XML data in the streamed XML data source, wherein the next portion of unevaluated XML data cannot comprise a subelement, attribute, or value that matches an unmatched step in the XPath expression;

skipping evaluation of all subelements, attributes, and values in the next portion of unevaluated XML data; and

generating a result based on the evaluation of the XPath expression.

19. The method of claim 18 wherein identifying a next portion of unevaluated XML data comprises:

loading a particular schema definition that corresponds to a previously matched step in the XPath expression; and

determining that the particular schema definition does not comprise a definition for a subelement, attribute, or value that potentially matches a step subsequent to the previously matched step in the XPath expression.

20. The method of claim 19 wherein determining that the particular schema definition does not comprise a definition for a potentially matching subelement, attribute, or value comprises analyzing occurrence constraints in the particular schema definition.

21. The method of claim 19 wherein determining that the particular schema definition does not comprise a definition for a potentially matching subelement, attribute, or value comprises analyzing value constraints in the particular schema definition.

22. The method of claim 19 wherein determining that the particular schema definition does not comprise a definition for a potentially matching subelement, attribute, or value comprises analyzing sequence constraints in the particular schema definition.

23. The method of claim 19 wherein determining that the particular schema definition does not comprise a definition for a potentially matching subelement, attribute, or value comprises analyzing type constraints in the particular schema definition.

24. The method of claim 18 wherein the portion of unevaluated XML data comprises all XML data remaining in the streamed XML data source, and further comprising terminating evaluation of the XPath expression on the streamed XML data source.

25. The method of claim 18 wherein skipping the portion of unevaluated XML data comprises sending instructions to an XML parser not to parse the portion of unevaluated XML data.

26. The method of claim 18, further comprising the step of compiling the XPath expression to form a compiled XPath expression, wherein the step of evaluating the XPath expression utilizes the compiled XPath expression.

27. The method of claim 26 wherein the step of identifying a next portion of unevaluated XML data comprises consulting instructions in the compiled XPath expression derived from the XML schema.

28. A computer-implemented method comprising the steps of:

receiving an XPath expression to be evaluated on a streamed XML data source, wherein the streamed XML data source is defined by an XML schema;

while evaluating the XPath expression on the streamed XML data source;

based at least upon information derived from the XML schema, identifying a target location in the streamed XML data source, wherein the target location comprises an element, attribute, or data value that potentially matches a next unmatched step in the XPath expression;

evaluating XML data from the streamed XML data source at the target location without evaluating any unevaluated XML data from the streamed XML data source located before the target location, wherein at least one unevaluated element, attribute, or data value is located before the target element; and

generating a result based on the evaluation of the XPath expression.

29. The method of claim 28 wherein identifying a next portion of unevaluated XML data comprises:

loading a particular schema definition that corresponds to a previously matched step in the XPath expression;

determining, as the target location, the index of a matching definition under the particular schema definition that defines a subelement, attribute, or value that potentially matches a next unmatched step in the XPath expression; and

determining that any unevaluated element occurring before the target location could not match a next unmatched step in the XPath expression.