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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00442250
Contributor : Joachim Niehren <>
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

File

CIAA.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00442250, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

496

Files downloads

303