inria-00348463, version 1
Bounded Delay and Concurrency for Earliest Query Answering
Olivier Gauwin 1, 2Joachim Niehren
1Sophie Tison 1, 2
3rd International Conference on Language and Automata Theory and Applications 5457 (2009) 350-361
Résumé : 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.
- 1 : MOSTRARE (INRIA Lille - Nord Europe)
- INRIA – CNRS : UMR8022 – Université Lille 1 - Sciences et Technologies : EA3588 – Université Charles de Gaulle - Lille III
- 2 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- Domaine : Informatique/Base de données
Informatique/Informatique et langage - Mots-clés : Tree Automata – Streaming – XML Databases
- inria-00348463, version 1
- http://hal.inria.fr/inria-00348463
- oai:hal.inria.fr:inria-00348463
- Contributeur : Olivier Gauwin
- Soumis le : Vendredi 19 Décembre 2008, 10:39:41
- Dernière modification le : Mardi 3 Novembre 2009, 16:51:01
Documents associés
Exporter