Polynomial Time Fragments of XPath with Variables

Abstract : Variables are the distiguishing new feature of XPath 2.0 which permits to select n-tuples of nodes in trees. It is known that the Core of XPath 2.0 captures n-ary first-order (FO) queries modulo linear time transformations. In this paper, we distinguish a fragment of Core XPath 2.0 that remains FO-complete with respect to n-ary queries while enjoying polynomial-time query answering.
Type de document :
Communication dans un congrès
26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun 2007, Beijing, China. pp.205-214, 2007
Liste complète des métadonnées


https://hal.inria.fr/inria-00135678
Contributeur : Joachim Niehren <>
Soumis le : mercredi 21 mars 2007 - 16:08:35
Dernière modification le : lundi 13 février 2017 - 18:00:08
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 12:40:46

Fichier

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

Identifiants

  • HAL Id : inria-00135678, version 1

Collections

Citation

Emmanuel Filiot, Joachim Niehren, Jean-Marc Talbot, Sophie Tison. Polynomial Time Fragments of XPath with Variables. 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun 2007, Beijing, China. pp.205-214, 2007. <inria-00135678>

Partager

Métriques

Consultations de
la notice

266

Téléchargements du document

169