Query Reasoning on Trees with Types, Interleaving, and Counting

Everardo Barcenas-Patino 1 Pierre Genevès 1 Nabil Layaïda 1 Alan Schmitt 2
1 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : A major challenge of query language design is the combination of expressivity with effective static analyses such as query containment. In the setting of XML, documents are seen as finite trees, whose structure may additionally be constrained by type constraints such as those described by an XML schema. We consider the problem of query containment in the presence of type constraints for a class of regular path queries extended with counting and interleaving operators. The counting operator restricts the number of occurrences of children nodes satisfying a given logical property. The interleaving operator provides a succinct notation for describing the absence of order between nodes satisfying a logical property. We provide a logic-based framework supporting these operators, which can be used to solve common query reasoning problems such as satisfiability and containment of queries in exponential time.
Type de document :
Communication dans un congrès
22nd International Joint Conference on Artificial Intelligence IJCAI'2011, Jul 2011, Barcelone, Spain. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00609556
Contributeur : Vincent Quint <>
Soumis le : mardi 19 juillet 2011 - 14:02:31
Dernière modification le : mercredi 29 novembre 2017 - 15:19:39
Document(s) archivé(s) le : lundi 12 novembre 2012 - 15:02:01

Fichier

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

Identifiants

  • HAL Id : inria-00609556, version 1

Collections

Citation

Everardo Barcenas-Patino, Pierre Genevès, Nabil Layaïda, Alan Schmitt. Query Reasoning on Trees with Types, Interleaving, and Counting. 22nd International Joint Conference on Artificial Intelligence IJCAI'2011, Jul 2011, Barcelone, Spain. 2011. 〈inria-00609556〉

Partager

Métriques

Consultations de la notice

797

Téléchargements de fichiers

167