inria-00390236, version 2
Earliest Query Answering for Deterministic Nested Word Automata
Olivier Gauwin
a, 1, 2Joachim Niehren 1, 2Sophie Tison b, 1, 2
17th International Symposium on Fundamentals of Computer Theory 5699 (2009) 121-132
Résumé : 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.
- a – INRIA
- b – Université des Sciences et Technologies de Lille - Lille I
- 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
- Versions disponibles : v1 (12-06-2009) v2 (13-08-2009)
- inria-00390236, version 2
- http://hal.inria.fr/inria-00390236
- oai:hal.inria.fr:inria-00390236
- Contributeur : Joachim Niehren
- Soumis le : Jeudi 13 Août 2009, 12:58:45
- Dernière modification le : Mardi 3 Novembre 2009, 16:45:41
Documents associés
Exporter