Streamable Fragments of Forward XPath

Olivier Gauwin 1, * Joachim Niehren 2, 3, *
Abstract : We present a query answering algorithm for a fragment of Forward XPath on XML streams that we obtain by compilation to deterministic nested word automata. Our algorithm is earliest and in polynomial time. This proves the finite streamability of the fragment of Forward XPath with child steps, outermost-descendant steps, label tests, negation, and conjunction (aka filters), under the reasonable assumption that the number of conjunctions is bounded. We also prove that finite streamability fails without this assumption except if P=NP.
Type de document :
Communication dans un congrès
16th International Conference on Implementation and Application of Automata, Jul 2011, Blois, France. pp.3-15, 2011
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00442250
Contributeur : Joachim Niehren <>
Soumis le : vendredi 29 avril 2011 - 17:42:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 30 juillet 2011 - 02:31:03

Fichier

CIAA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00442250, version 1

Collections

Citation

Olivier Gauwin, Joachim Niehren. Streamable Fragments of Forward XPath. 16th International Conference on Implementation and Application of Automata, Jul 2011, Blois, France. pp.3-15, 2011. 〈inria-00442250〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

125