Earliest Query Answering for Deterministic Nested Word Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Earliest Query Answering for Deterministic Nested Word Automata

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.
Fichier principal
Vignette du fichier
0.pdf (292.46 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00390236 , version 1 (12-06-2009)
inria-00390236 , version 2 (13-08-2009)

Identifiants

  • HAL Id : inria-00390236 , version 1

Citer

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. ⟨inria-00390236v1⟩

Collections

LIFL
189 Consultations
272 Téléchargements

Partager

Gmail Facebook X LinkedIn More