OPTIMIZED STREAMING EVALUATION OF XML QUERIES

• US 20090125495A1
• Filed: 11/09/2007
• Published: 05/14/2009
• Est. Priority Date: 11/09/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Zhang, Ning, Idicula, Sam, Chandrasekar, Sivasankaran, Agarwal, Nipun
• Granted Patent: US 8,250,062 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format

Abstract

A database system may perform a streaming evaluation of an XPath expression by utilizing an XPath evaluation component in tandem with an XML event-streaming component. For a more optimal filtered streaming evaluation, the XML event-streaming component may provide an interface whereby the evaluation component sends certain criteria to the event-streaming component when requesting an XML event. The criteria may be based on a next unmatched step in the XPath expression. In response to the request for an XML event, the event-streaming component may only return events that match the criteria. The evaluation component may be, for example, a compiled state machine for the XPath expression. The criteria may be pre-compiled for each possible state in the state machine. The event-streaming component may also utilize the criteria along with schema information to skip parsing of certain segments of XML data.

Claims

1. A computer-implemented method for evaluating XPath expressions, comprising the steps of:

(1) sending criteria from an XPath evaluation component to an XML event-streaming component;

wherein the criteria is based at least upon a next unmatched step in an XPath expression;

(2) streaming an XML event from the XML event-streaming component to the XPath evaluation component;

wherein the XML event-streaming component determines the XML event based on the criteria;

(3) matching the XML event to said next unmatched step in the XPath expression;

(4) repeating steps 1-3 with respect to a new next unmatched step in the XPath expression, until it is determined that there are no remaining unmatched steps in the XPath expression; and

(5) outputting an XPath result based at least upon the XML event streamed in the last iteration of step 2.

2. The method of claim 1 wherein the XML evaluation component is a state machine compiled for at least the XPath expression.

3. The method of claim 2 wherein the state machine maintains state information indicating one or more current states based on previously received XML events, wherein the next unmatched step corresponds to state transitions away from the one or more current states.

4. The method of claim 3 wherein, for each state in the state machine, the state machine stores pre-compiled criteria, wherein the criteria sent in step 1 comprises the pre-compiled criteria for the one or more current states, wherein the pre-compiled criteria was generated when the state machine was compiled.

5. The method of claim 3 wherein:

matching the XML event to said next unmatched step comprises changing the state information to indicate a new one or more current states;

determining that there are no remaining unmatched steps in the XPath expression comprises determining that a current state is an accepting state; and

outputting an XPath result comprises;

the XPath evaluation component receiving one or more events while in the accepting state;

outputting XML for all XML events received while in the accepting state; and

receiving a closing XML event that causes the state machine to regress to a non-accepting state.

6. The method of claim 3 wherein the state machine further comprises gamma transitions operating in reverse of the state transitions and based on events that signal the end of an element.

7. The method of claim 2 wherein the state machine is a non-deterministic finite automaton.

8. The method of claim 1 further comprising the steps of:

inputting one or more XML data sources into the XML event-streaming component; and

generating the XML event based on an element, attribute, or value the XML event-streaming component parses from the one or more XML data sources.

9. The method of claim 8 wherein the one or more XML data sources is formatted as binary-encoded XML, further comprising the step of:

prior to generating the XML event, decoding a portion of an XML data source with the XML event-streaming component, wherein the XML event is generated based on an element, attribute, or value in said portion.

10. The method of claim 8, wherein the one or more XML data sources is based on an XML schema, further comprising the steps of, prior to generating an XML event:

at the XML event-streaming component, determining that, based on the criteria and the XML schema, no XML event matching the criteria may be generated from a portion of an XML data source; and

skipping the parsing of said portion.

11. The method of claim 1, wherein the XML event comprises at least one element, attribute, or value.

12. The method of claim 1, wherein the XML event is an XML SAX event.

13. The method of claim 1, wherein the criteria comprise at least the name of an element or attribute, a comparison operation based on value, or a structural relationship.

14. The method of claim 1, further comprising the steps of, prior to step 1:

receiving an XML Query;

normalizing the XML Query to generate the XPath expression; and

initiating evaluation of the XPath expression by the XPath evaluation component.

15. The method of claim 1, wherein step 5 comprises:

the XML evaluation component receiving one or more XML events;

outputting XML for the one or more XML events; and

receiving an XML event indicating the end of a particular element, wherein the beginning of the particular element was indicated by the XML event streamed in the last iteration of step 2.

16. The method of claim 1, wherein the criteria is further based upon a next unmatched step in one or more additional XPath expressions.

17. The method of claim 16, wherein the XPath expression and the one or more additional XPath expressions are normalized from a same XML Query.

18. The method of claim 1 wherein the evaluation component comprises a compiled representation of the XPath expression, wherein the compiled representation comprises, for each step of the XPath expression, pre-compiled criteria, wherein the criteria sent in step 1 comprises the pre-compiled criteria for the next unmatched step.

21. A computer-readable storage medium storing instructions for performing the method recited in claim 1.

22. A computer-readable storage medium storing instructions for performing the method recited in claim 2.

23. A computer-readable storage medium storing instructions for performing the method recited in claim 18.

19. A method for evaluating an XPath expression comprising the computer-implemented steps of:

compiling a state machine based on an XPath expression, the state machine comprising states and transitions that reflect the steps of the XPath expression;

evaluating the XPath expression using the state machine, wherein the step of evaluating comprises;

receiving one or more XML events from an XML event-streaming component;

maintaining state information based on the content and ordering of the one or more XML events, wherein the state information indicates a current state in the state machine;

based at least upon transitions from the current state to subsequent states, determining criteria, wherein the criteria describes characteristics of any XML event that will transition the state machine to at least one of the subsequent states;

requesting, from the XML event-streaming component, a next XML event that meets the criteria;

in response to said requesting, receiving an XML event from the XML streaming component that meets the criteria; and

generating an XPath result based on the evaluation.

24. A computer-readable storage medium storing instructions for performing the method recited in claim 19.

20. A computer-implemented method for evaluating an XML query, comprising the steps of:

compiling a state machine based on one or more XPath expressions;

wherein the state machine comprises a first set of states, a set of transitions, and a set of conditions;

wherein each transition in the set of transitions indicates a transformation from a state in the first set of states to a state in a second set of states;

wherein each condition in the set of conditions describes, for a distinct transition in the set of transitions, criteria under which input received by the state machine will result in the distinct transition; and

while executing the state machine in the first set of states;

sending data from the state machine to an XML event-streaming component indicating the set of conditions;

parsing an XML data source with the XML event-streaming component until the XML streaming engine generates an event that meets the criteria of at least one condition in the set of conditions;

sending input from the XML event-streaming component to the state machine indicating the event; and

based on the event, transitioning the state machine to a third set of states, wherein the third set of states comprises an accepting state, wherein the state machine outputs the XML event as an XPath result.

25. A computer-readable storage medium storing instructions for performing the method recited in claim 20.