1. A method for evaluation of XPath expressions over XML documents, where said method applied to an input XPath expression, called input query, comprises: (a) using one or more data structures for computing 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) computing 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 can be efficiently evaluated over XML documents.