An Evaluation of Regular Path Expressions with Qualifiers against XML Streams

This paper presents SPEX, a streamed and progressive evaluation of regular path expressions with XPath-like qual-ifiers against XML streams. SPEX proceeds as follows. An expression is translated in linear time into a network of transducers, most of them having 1-DPDT equivalents. Every stream message is then processed once by the entire network and result fragments are output on the fly. In most practical cases SPEX needs a time linear in the stream size and for transducer stacks a memory quadratic in the stream depth. Experiments with a prototype implementation point to a very good efficiency of the SPEX approach.