Bounded Delay and Concurrency for Earliest Query Answering

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.

Mots clés

Tree Automata Streaming XML Databases

Domaines

Base de données [cs.DB] Informatique et langage [cs.CL]

Fichier principal

lata09_paper.pdf (178.37 Ko)

lata09_extended.pdf (238.8 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Format : Autre

Olivier Gauwin : Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00348463

Soumis le : vendredi 19 décembre 2008-10:39:41

Dernière modification le : vendredi 24 mars 2023-14:52:51

Archivage à long terme le : mardi 8 juin 2010-16:44:18

Dates et versions

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

Identifiants

HAL Id : inria-00348463 , version 1
DOI : 10.1007/978-3-642-00982-2

Citer

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⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA LIFL MOSTRARE INRIA2 ANR

313 Consultations

331 Téléchargements