Patent ID: 7979423

Claim:
A method for constructing tuples for a query, comprising: receiving, with a computer including a processor, the query, wherein the query is formed by one or more paths, and wherein each path includes one or more steps, wherein a query structure represents the query, wherein the query structure includes query nodes, and wherein one or more of the query nodes is flagged with a FOR binding or a LET binding; receiving a hierarchical document including one or more document nodes; precomputing information to be used in processing the query to determine which step instance match candidates are to be paired, in which order the step instance match candidates are to be paired to form tuples, and which ancestors should be compared for each pair of the step instance match candidates; determining a query node with the FOR binding from among the query nodes that is a deepest nearest common FOR ancestor using the query structure for extraction entries for a pair of document nodes to be extracted by processing the query, wherein each of the extraction entries includes a step instance match candidate identifying a document node from among the document nodes and a step instance ancestor path for the document node, wherein the deepest nearest common FOR ancestor is a nearest common FOR ancestor that is farther from a root node of the query structure than other common FOR ancestors; and processing the query to construct results using the deepest nearest common FOR ancestor and the precomputed information by, after a first pairing of the step instance match candidates of a first result, when doing subsequent pairings, pairing a new step instance match candidate with an already paired step instance match candidate that has a deepest nearest common FOR ancestor.