Patent ID: 7219091

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