Patent ID: 7483887
Filing Date: 2009-01-27
Classification: G06F,Y10S

Abstract:
1. A method of computing an answer to query twig pattern, comprising: determining a plurality of streams associated with the query twig pattern; determining whether a first set of streams of the plurality of stream is not empty; retrieving a next node in the first set of streams, if not empty, and verifying that the next node has a descendant node in each of the first set of streams associated with the query twig pattern; recursively verifying that the descendant node has a further descendant node in each of the set of streams associated with the query twig pattern; cleaning a stack containing partial solutions corresponding to a parent node of the next node if a root node or a stack associated with a parent node of the next node is not empty; cleaning the stack associated with the next node if the next node is a root node or the stack associated with the patent node of the next node is not empty, otherwise advancing the stream containing the next node; after cleaning the stack associated with the next node, adding the next node to the stack containing partial solutions; and advancing the stream containing the next node if the next node is not a leaf node, otherwise, generating a solution to the query twig pattern.