... because the compressed grammar need only be traversed once. For instance, tree automata and Core XPath can be evaluated in one pass over straight-line tree (SLT) grammars [20]. This idea was used in =-=[11]-=- for selectivity estimation of structural XPath. They study synopsis size and accuracy, but do not consider efficient evaluation. We combine the ideas of [24, 1] with that of evaluating in one pass ov...