Method and apparatus for XML query evaluation using early-outs and multiple passes
First Claim
1. A computer program product comprising a computer readable storage medium having computer usable program code programmed for Extensible Mark-up Language (“
- XML”
) query evaluation using early-outs and multiple passes, the computer program product having operations comprising;
rewriting, by way of a processor executing instructions of a memory, an alterable XML query comprising multiple steps such that less selective steps of the XML query will be evaluated after more selective steps, wherein the XML query comprises logical expressions formatted according to one of an XPath expression language and an XQuery query language;
selectively evaluating the steps in the rewritten XML query using a multi-pass evaluation procedure to traverse the XML document, wherein the multi-pass evaluation procedure evaluates at least one step in the rewritten XML query with each pass through the XML document until veracity of the rewritten XML query is established; and
exiting the multi-pass evaluation procedure in response to determining that an XML document meets an exitable condition of the XML query, the exitable condition comprising a determination that the veracity of the XML query for a first predicate logically applies to the remaining predicates without evaluating the remaining steps of the XML query.
5 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus is disclosed for XML query evaluation using early-outs and multiple passes to evaluate an XML query. A multi-pass evaluation procedure evaluates the XML query one step at a time as needed to complete evaluation. The multi-pass evaluation procedure evaluates XML queries containing logical expressions such as “AND” expressions, “OR” expressions, and implied “AND” expressions within “FOR” clauses. Queries containing logical expressions are often satisfied before every component is evaluated. Thus, executing the multi-pass evaluation procedure allows the evaluation to exit early when the veracity of the query is determined, not necessarily when every component has been evaluated. The multi-pass evaluation procedure executes as long as a descendant axis of the XML query need not be evaluated past a child node. When evaluation of a descendant axis past a child node is required, the multi-pass evaluation procedure may switch to a single-pass evaluation procedure to complete evaluation.
-
Citations
11 Claims
-
1. A computer program product comprising a computer readable storage medium having computer usable program code programmed for Extensible Mark-up Language (“
- XML”
) query evaluation using early-outs and multiple passes, the computer program product having operations comprising;rewriting, by way of a processor executing instructions of a memory, an alterable XML query comprising multiple steps such that less selective steps of the XML query will be evaluated after more selective steps, wherein the XML query comprises logical expressions formatted according to one of an XPath expression language and an XQuery query language; selectively evaluating the steps in the rewritten XML query using a multi-pass evaluation procedure to traverse the XML document, wherein the multi-pass evaluation procedure evaluates at least one step in the rewritten XML query with each pass through the XML document until veracity of the rewritten XML query is established; and exiting the multi-pass evaluation procedure in response to determining that an XML document meets an exitable condition of the XML query, the exitable condition comprising a determination that the veracity of the XML query for a first predicate logically applies to the remaining predicates without evaluating the remaining steps of the XML query. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- XML”
-
8. An apparatus for Extensible Mark-up Language (“
- XML”
) query evaluation using early-outs and multiple passes, the apparatus comprising;a processor coupled to a memory, the memory comprising a rewrite module configured to rewrite an alterable XML query comprising multiple steps such that less selective steps of the XML query are evaluated after more selective steps, wherein the XML query comprises logical expressions formatted according to one of an XPath expression language and an XQuery query language; an evaluation module configured to selectively evaluate the steps in the rewritten XML query using a multi-pass evaluation procedure to traverse the XML document, wherein the multi-pass evaluation procedure evaluates at least one step in the rewritten XML query with each pass through the XML document until veracity of the rewritten XML query is established; and an exit module configured to exit the multi-pass evaluation procedure in response to determining that an XML document meets an exitable condition of the XML query, the exitable condition comprising a determination that the veracity of the XML query for a first predicate logically applies to the remaining predicates without evaluating the remaining steps of the XML query. - View Dependent Claims (9, 10, 11)
- XML”
Specification