Earliest Query Answering for Deterministic Nested Word Automata

Abstract : Earliest query answering (EQA) is an objective of many recent streaming algorithms for XML query answering, that aim for close to optimal memory management. In this paper, we show that EQA is infeasible even for a small fragment of Forward XPath except if P=NP. We then present an EQA algorithm for queries and schemas defined by deterministic nested word automata (dNWAs) and distinguish a large class of dNWAs for which streaming query answering is feasible in polynomial space and time.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00390236
Contributor : Joachim Niehren <>
Submitted on : Thursday, August 13, 2009 - 12:58:45 PM
Last modification on : Thursday, July 25, 2019 - 8:50:03 AM
Long-term archiving on : Wednesday, September 22, 2010 - 1:25:08 PM

File

0.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00390236, version 2

Collections

Citation

Olivier Gauwin, Joachim Niehren, Sophie Tison. Earliest Query Answering for Deterministic Nested Word Automata. 17th International Symposium on Fundamentals of Computer Theory, Sep 2009, Wraclaw, Poland. pp.121-132. ⟨inria-00390236v2⟩

Share

Metrics

Record views

338

Files downloads

538