Processing XPath queries with forward and downward axes over XML streams

We propose an XPath processing algorithm that efficiently evaluates XPath queries in XP {↓, →, *, []} over XML streams. An XPath query is expressed with axes, which are binary relations between nodes in XML streams: '↓' identifies the child/descendant axes and '→' indicates the following/following-sibling axes. The proposed algorithm evaluates XPath queries within one XML parsing pass and outputs the fragments found in XML streams as the query results. The difficulty of XP {↓, →, *, []} evaluation lies in establishing dynamic scope control for the following/following-sibling axes. The algorithm uses double-layered non-deterministic finite automata (NFA) to resolve this issue. First layer NFA is compiled from XPath queries and is able to evaluate sub-queries in XP {↓, →, *} . Second layer NFA handles predicate parts. It is dynamically maintained during XML parsing: a state is constructed from a pair of the corresponding state in the first layer automaton and the currently parsed node in the XML stream. Layered NFA achieves O (| D || Q |) time complexity by introducing a state sharing technique, which avoids the exponential growth in the state size of Layered NFA by eliminating redundant transitions. We validate the efficiency of the algorithm through empirical experiments and show that Layered NFA is up to four times faster, and twice as fast on average, than existing algorithms.