Efficient processing of XPath queries
OwnerGeorg Gottlob, Christoph Koch +1inventors
InventorsGeorg Gottlob, Christoph Koch, Reinhard Pichler
Life of this patent
Estimating the term…
Abstract
The disclosed teachings provide methods and systems for efficient evaluation of XPath queries. In particular, the disclosed evaluation methods require only polynomial time with respect to the total size of an input XPath query and an input XML document. Crucial for the new methods is the notion of “context-value tables”. This idea can be further refined for queries in Core XPath and XSLT Patterns so as to yield even a linear time evaluation method. Moreover, the disclosed methods can be used for improving existing methods and systems for processing XPath expressions so to guarantee polynomial worst-case complexity.
Claims77
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.
A computer-implemented method for evaluation of an XPath expression for reducing time complexity to polynomial time, called input query, on an XML document for web pages, called input document, with respect to a given context, called input context, said method comprising:
- (a) using of one or more data structures, jointly called data pool, for memorizing and retrieving results of evaluations of subexpressions of said input query with respect to a plurality of contexts;
- (b) one or more subordinate methods, jointly called basic-creating, for evaluation of a basic set of XPath expressions, called basic fragment, said basic fragment including atomic XPath expressions, whereby XPath expressions belonging to said basic fragment are generated directly over said input document, without recurring to evaluations of subexpressions;
- (c) one or more subordinate methods, jointly called compound-evaluation, for generating a compound XPath expression with respect to a given context, such that said compound-evaluation generates a result of said compound XPath expression over said input-document with respect to said context by suitably obtaining and combining results of evaluations of subexpressions of said compound XPath expression with respect to a plurality of contexts, where subexpressions belonging to said basic fragment are evaluated by said basic-evaluation, and where compound subexpressions are in turn evaluated by said compound-evaluation, and where multiple evaluations of a same subexpression with respect to a same context are avoided by storing said results of evaluations of subexpressions in said data pool and by retrieving stored results from said data pool when needed;
- (d) answering said input query with respect to said context over said input document by applying said basic-evaluation to said input query in case said input query belongs to said basic fragment, arid by applying said compound-evaluation to said input query in case said input query is a compound XPath expression;
- whereby XPath expressions are efficiently generated of web pages for reducing time complexity to polynomial time over XML documents.
A system for evaluation of an XPath expression, called input query, on an XML document, called input document, with respect to a given context, called input context, said system comprising:
- (a) a data storage device and means for storing and manipulating one or more data structures, jointly called data pool, for memorizing and retrieving results of evaluations of subexpressions of said input query with respect to a plurality of contexts;
- (b) means, called basic-evaluation-means, for evaluation of a basic set of XPath expressions, called basic fragment, including atomic XPath expressions, whereby XPath expressions belonging to said basic fragment are evaluated directly over said input document, without recurring to evaluations of subexpressions;
- (c) means, called compound-evaluation-means, for evaluating a compound XPath expression with respect to a given context, such that said compound-evaluation-means compute a result of said compound XPath expression over said input-document with respect to said context by suitably obtaining and combining results of evaluations of subexpressions of said compound XPath expression with respect to a plurality of contexts, where subexpressions belonging to said basic fragment are evaluated by said basic-evaluation, and where compound subexpressions are in turn evaluated by said compound-evaluation-means, and where multiple evaluations of a same subexpression with respect to a same context are avoided by storing said results in said data pool and by retrieving stored results from said data pool when needed;
- (d) answering said input query with respect to said context over said input document by applying said basic-evaluation-means to said input query in case said input query belongs to said basic fragment, and by applying said compound-evaluation-means to said input query in case said input query is a compound XPath expression;
- whereby XPath expressions can be efficiently evaluated over XML documents.
A computer-implemented system for evaluation of XPath expressions for reducing time complexity to polynomial time, said XPath expressions being also known as XML Path expressions, over XML documents, said system comprising:
- (a) a data storage device and one or more data structures, said data structures being used for computing and storing results of evaluations of subexpressions of an input XPath expression, called 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) means for computation of a result of said evaluation of said input query by building and combining evaluations of said subexpressions, where an order of said building and combining is obtained from 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 over which said XPath expression are evaluated for reducing time complexity to polynomial time.
Dependencies are inferred from the claim text.