Patent ID: 7499921

Claim:
A method for processing an XML document, wherein said XML document comprises a tree structure comprising branches comprising a plurality of nodes, the method comprising steps of: receiving a query comprising a relative XPath expression relative to a context node, the query comprising search criteria and wherein the search criteria comprise a set of constraints that specify forward and backward relations between nodes; receiving at least a portion of the XML document; receiving the context node from the XML document with respect to which the search criteria are applied; evaluating the relative XPath expression relative to the context node by producing a modified X-DAG of the at least a portion of the XML document, wherein the modified X-DAG is a graph representation of the at least a portion of the XML document generated from the XPath expression, representing the XPath expression and its constraints; and wherein the modified X-DAG comprises a “ctxt” node that only matches the context node; and wherein the modified X-DAG converts backward constraints into forward constraints; modifying the search criteria in the query to introduce constraints relative to the “ctxt” node into the set of constraints; searching the modified query over the modified X-DAG, beginning at a root node, processing the modified X-DAG in a streaming manner in a single depth-first traversal of the modified X-DAG; and locating one or more nodes that satisfy the modified search criteria.