Patent ID: 8015179

Claim:
A method of query pattern matching, comprising: (a) generating a list of potential ancestors and a list of potential descendants; (b) sorting the list of potential ancestors and the list of potential descendants in an order of a start position attribute in a database; (c) determining whether input lists are not empty and whether a stack is not empty; (d) determining, based upon a result from (c), whether a start position of a current node of the list of potential ancestors is greater than an end position of a node on a top of the stack and a start position of a current node of the list of potential descendants is greater than the end position of the node on the top of the stack; (e) popping the stack for a first result from (d) and for a second result from (d) determining whether the start position of the current node of the list of potential ancestors is less than the start position of the current node of the list of potential descendents; and (f) pushing the current node of the list of potential ancestors onto the stack and looking to a next node of the list of potential ancestors for a first result from (e) and appending matches to an output list and looking to a next node in the list of potential descendants for a second result from (e).