Patent ID: 7162485
Filing Date: 2007-01-09
Classification: G06F,Y10S

Abstract:
1. A computer-implemented method for evaluation of XPath expressions for reducing time complexity to polynomial time over XML documents for web pages, where said method applied to an input XPath expression, called input query, comprises: (a) using one or more data structures for generating and storing results of evaluations of subexpressions of said input query with respect to a plurality of contexts, whereby multiple evaluations of a subexpression with respect to a same context are avoided, and (b) generating a result of said evaluation of said input query by building and combining evaluations of said subexpressions, according to an order induced by a hierarchical structure of said input query; whereby XPath expressions are evaluated in polynomial time in the sum of the size of said XPath expression and the size of an underlying XML document for web over pages which said XPath expression for reduced time complexity to polynomial time are evaluated.