Optimized streaming evaluation of XML queries
First Claim
1. A computer-implemented method comprising the steps of:
- (1) during evaluation of at least a first XPath expression comprising a plurality of steps, an XPath evaluation component identifying a next unmatched step in the plurality of steps;
(2) the XPath evaluation component sending an event request to an XML event-streaming component;
wherein the event request includes one or more criteria that specify a characteristic of at least a first XML event that will satisfy the next unmatched step;
wherein the XML event-streaming component is separate from the XPath evaluation component;
(3) in response to the event request, the XML event-streaming component streaming an XML event to the XPath evaluation component;
wherein the XML event-streaming component determines the XML event to stream to the XPath evaluation component based on the specified characteristic of at least the first XML event that will satisfy the next unmatched step;
(4) the XPath evaluation component matching the XML event to said next unmatched step;
(5) repeating steps 1-4 with respect to at least a new next unmatched step in the first XPath expression, until the XPath evaluation component determines that there are no remaining unmatched steps in the first XPath expression; and
(6) outputting an XPath result based at least upon the XML event streamed in the last iteration of step 3;
wherein the method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
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.
183 Citations
56 Claims
-
1. A computer-implemented method comprising the steps of:
-
(1) during evaluation of at least a first XPath expression comprising a plurality of steps, an XPath evaluation component identifying a next unmatched step in the plurality of steps; (2) the XPath evaluation component sending an event request to an XML event-streaming component; wherein the event request includes one or more criteria that specify a characteristic of at least a first XML event that will satisfy the next unmatched step; wherein the XML event-streaming component is separate from the XPath evaluation component; (3) in response to the event request, the XML event-streaming component streaming an XML event to the XPath evaluation component; wherein the XML event-streaming component determines the XML event to stream to the XPath evaluation component based on the specified characteristic of at least the first XML event that will satisfy the next unmatched step; (4) the XPath evaluation component matching the XML event to said next unmatched step; (5) repeating steps 1-4 with respect to at least a new next unmatched step in the first XPath expression, until the XPath evaluation component determines that there are no remaining unmatched steps in the first XPath expression; and (6) outputting an XPath result based at least upon the XML event streamed in the last iteration of step 3; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. 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, while executing the state machine; 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 one or more criteria, wherein the one or more criteria describe characteristics of any XML event that will transition the state machine to at least one of the subsequent states; sending the one or more criteria to the XML event-streaming component; requesting, from the XML event-streaming component, a next XML event that meets the one or more criteria; in response to said requesting, receiving an XML event from the XML streaming component that meets the one or more criteria; and generating an XPath result based on the evaluation; wherein the method is performed by one or more computing devices. - View Dependent Claims (19, 20, 21)
-
-
18. 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, one or more 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 one or more 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; wherein the method is performed by one or more computing devices. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
-
-
29. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause:
-
(1) during evaluation of at least a first XPath expression comprising a plurality of steps, an XPath evaluation component identifying a next unmatched step in the plurality of steps; (2) the XPath evaluation component sending an event request to an XML event-streaming component; wherein the event request includes one or more criteria that specify a characteristic of at least a first XML event that will satisfy the next unmatched step; wherein the XML event-streaming component is separate from the XPath evaluation component; (3) in response to the event request, the XML event-streaming component streaming an XML event to the XPath evaluation component; wherein the XML event-streaming component determines the XML event to stream to the XPath evaluation component based on the specified characteristic of at least the first XML event that will satisfy the next unmatched step; (4) the XPath evaluation component matching the XML event to said next unmatched step; (5) repeating steps 1-4 with respect to at least a new next unmatched step in the first XPath expression, until the XPath evaluation component determines that there are no remaining unmatched steps in the first XPath expression; and (6) outputting an XPath result based at least upon the XML event streamed in the last iteration of step 3; wherein the method is performed by one or more computing devices. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
-
-
45. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause:
-
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, while executing the state machine; 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 one or more criteria, wherein the one or more criteria describe characteristics of any XML event that will transition the state machine to at least one of the subsequent states; sending the one or more criteria to the XML event-streaming component; requesting, from the XML event-streaming component, a next XML event that meets the one or more criteria; in response to said requesting, receiving an XML event from the XML streaming component that meets the one or more criteria; and generating an XPath result based on the evaluation; wherein the method is performed by one or more computing devices. - View Dependent Claims (47, 48, 49)
-
-
46. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computing devices, cause:
-
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, one or more 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 one or more 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; wherein the method is performed by one or more computing devices - View Dependent Claims (50, 51, 52, 53, 54, 55, 56)
-
Specification