Skip to Main content Skip to Navigation
Conference papers

Streamable Fragments of Forward XPath

Olivier Gauwin 1, * Joachim Niehren 2, 3, *
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Friday, April 29, 2011 - 5:42:58 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on: : Saturday, July 30, 2011 - 2:31:03 AM


Files produced by the author(s)


  • 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⟩



Record views


Files downloads