Bounded Delay and Concurrency for Earliest Query Answering - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2009

Bounded Delay and Concurrency for Earliest Query Answering

Abstract

Earliest query answering is needed for streaming XML processing with optimal memory management. We study the feasibility of earliest query answering for node selection queries. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection. We show that both properties are decidable in polynomial time for queries defined by deterministic automata for unranked trees. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees.
Fichier principal
Vignette du fichier
lata09_paper.pdf (178.37 Ko) Télécharger le fichier
lata09_extended.pdf (238.8 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other
Loading...

Dates and versions

inria-00348463 , version 1 (19-12-2008)

Identifiers

Cite

Olivier Gauwin, Joachim Niehren, Sophie Tison. Bounded Delay and Concurrency for Earliest Query Answering. 3rd International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. pp.350-361, ⟨10.1007/978-3-642-00982-2⟩. ⟨inria-00348463⟩
313 View
330 Download

Altmetric

Share

Gmail Facebook X LinkedIn More