Query evaluation using ancestor information

1. A method for processing 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;

receiving a hierarchical document including one or more document nodes; and

while processing the query and traversing the hierarchical document,

constructing a structure, wherein the structure includes structure nodes, and wherein each of the structure nodes includes a next step in a path of the query, a level for a next step instance, a parent step instance identifier of a next step instance, and a matched step instance identifier when a match is found;

constructing one or more extraction entries by traversing the structure bottom up, starting from a last structure node and continuing up to a root node of the structure while propagating up parent step instance identifier information to form a step instance ancestor path, wherein each of the one or more extraction entries includes a step instance match candidate identifying a document node and the step instance ancestor path for the document node; and

constructing one or more tuples using the one or more extraction entries by associating the step instance match candidate from one of the one or more extraction entries with the step instance match candidate from at least one of the one or more other extraction entries.

2. The method of claim 1 , further comprising:

flagging flush points in a query structure associated with the query; and

upon reaching the flush points while processing the query,

returning a portion of results generated using one or more of the extraction entries; and

discarding the used one or more extraction entries.

3. The method of claim 1 , wherein the query is processed to find document nodes in the hierarchical document that are described by the one or more steps of the one or more paths in the query.

4. The method of claim 1 , wherein the structure is a LookingFor structure.

5. The method of claim 1 , wherein each of the one or more extraction entries includes the level of a corresponding step instance match candidate.

6. A computer program product for processing a query comprising a non-transitory computer-readable medium storing a computer readable program, wherein the computer readable program, when executed by a processor on a computer, causes the computer to:

receive the query, wherein the query is formed by one or more paths, and wherein each path includes one or more steps;

receive a hierarchical document including one or more document nodes; and

while processing the query and traversing the hierarchical document,

constructing a structure, wherein the structure includes structure nodes, and wherein each of the structure nodes includes a next step in a path of the query, a level for a next step instance, a parent step instance identifier of a next step instance, and a matched step instance identifier when a match is found;

construct one or more extraction entries by traversing the structure bottom up, starting from a last structure node and continuing up to a root node of the structure while propagating up parent step instance identifier information to form a step instance ancestor path, wherein each of the one or more extraction entries includes a step instance match candidate identifying a document node and the step instance ancestor path for the document node; and

construct one or more tuples using the one or more extraction entries by associating the step instance match candidate from one of the one or more extraction entries with the step instance match candidate from at least one of the one or more other extraction entries.

7. The computer program product of claim 6 , wherein the computer readable program when executed on a computer causes the computer to:

flag flush points in a query structure associated with the query; and

upon reaching the flush points while processing the query,

return a portion of results generated using one or more of the extraction entries; and

discard the used one or more extraction entries.

8. The computer program product of claim 6 , wherein the query is processed to find document nodes in the hierarchical document that are described by the one or more steps of the one or more paths in the query.

9. The computer program product of claim 6 , wherein the structure is a LookingFor structure.

10. The computer program product of claim 6 , wherein each of the one or more extraction entries includes the level of a corresponding step instance match candidate.

11. A system for processing a query, comprising:

a processor; and

storage coupled to the processor, wherein the storage stores a computer program, and wherein the processor is configured to execute the computer program to perform operations, and wherein the operations comprise:

receiving the query, wherein the query is formed by one or more paths, and wherein each path includes one or more steps;

receiving a hierarchical document including one or more document nodes;

while processing the query and traversing the hierarchical document,

constructing a structure, wherein the structure includes structure nodes, and wherein each of the structure nodes includes a next step in a path of the query, a level for a next step instance, a parent step instance identifier of a next step instance, and a matched step instance identifier when a match is found;

constructing one or more extraction entries by traversing the structure bottom up, starting from a last structure node and continuing up to a root node of the structure while propagating up parent step instance identifier to form a step instance ancestor path, wherein each of the one or more extraction entries includes a step instance match candidate identifying a document node and the step instance ancestor path for the document node; and

constructing one or more tuples using the one or more extraction entries by associating the step instance match candidate from one of the one or more extraction entries with the step instance match candidate from at least one of the one or more other extraction entries.

12. The system of claim 11 , wherein the operations further comprise:

flagging flush points in a query structure associated with the query; and

upon reaching the flush points while processing the query,

returning a portion of results generated using one or more of the extraction entries; and

discarding the used one or more extraction entries.

13. The system of claim 11 , wherein the query is processed to find document nodes in the hierarchical document that are described by the one or more steps of the one or more paths in the query.

14. The system of claim 11 , wherein the structure is a LookingFor structure.

15. The system of claim 11 , wherein each of the one or more extraction entries includes the level of a corresponding step instance match candidate.