Methods and apparatus are provided for evaluating XPath filters on fragmented and distributed XML documents. According to one aspect of the invention, a method is disclosed for evaluating a query over a tree having a plurality of fragments distributed over a plurality of sites. The method comprises the steps of identifying the plurality of sites storing at least one of the plurality of fragments of the tree; providing the query to the plurality of identified sites, wherein each of the identified sites partially evaluates the query against one of more fragments of the tree stored by the respective site; obtaining partial results from the plurality of identified sites; and composing the partial results to compute a result to the query. The query may be, for example, a boolean XPath query. The method can be performed, for example, by a coordinating site that stores a root fragment of the tree.