Patent ID: 7454415

Claim:
A method of computing an answer to a query path pattern, comprising: determining whether a first set of streams in a subtree rooted at a node q is empty; and if so, then terminating the method and if not, then the method comprises: (a) retrieving a first node in the first set of streams having a minimum ordering value; (b) removing partial answers that cannot extend to full answers from a stack associated with the first node; (c) augmenting remaining partial answers with a further stream node; (d) determining whether the further stream node is a leaf node; and (e) producing solutions if the further stream stream node is a leaf node, and if the first node is not a leaf node, returning to step (a); associating nodes in a query pattern with respective streams containing positional attributes, wherein the minimum ordering value is for a first one of the positional attributes; associating a respective stack to each node in the query pattern; and sorting the stream nodes according to a first one of the positional attributes.