Streamable Fragments of Forward XPath - Archive ouverte HAL Access content directly
Conference Papers Year : 2011

Streamable Fragments of Forward XPath

(1) , (2, 3)


We present a query answering algorithm for a fragment of Forward XPath on XML streams that we obtain by compilation to deterministic nested word automata. Our algorithm is earliest and in polynomial time. This proves the finite streamability of the fragment of Forward XPath with child steps, outermost-descendant steps, label tests, negation, and conjunction (aka filters), under the reasonable assumption that the number of conjunctions is bounded. We also prove that finite streamability fails without this assumption except if P=NP.
Fichier principal
Vignette du fichier
CIAA.pdf (200.46 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00442250 , version 1 (29-04-2011)


  • HAL Id : inria-00442250 , version 1


Olivier Gauwin, Joachim Niehren. Streamable Fragments of Forward XPath. 16th International Conference on Implementation and Application of Automata, Jul 2011, Blois, France. pp.3-15. ⟨inria-00442250⟩
259 View
176 Download


Gmail Facebook Twitter LinkedIn More