Highly expressive query languages for unordered data trees

Serge Abiteboul 1, 2 Pierre Bourhis 3 Victor Vianu 4
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We study highly expressive query languages for unordered data trees, using as formal vehicles Active XML and exten- sions of languages in the while family. All languages may be seen as adding some form of control on top of a set of basic pattern queries. The results highlight the impact and interplay of different factors: the expressive power of ba- sic queries, the embedding of computation into data (as in Active XML), and the use of deterministic vs. nondeter- ministic control. All languages are Turing complete, but not necessarily query complete in the sense of Chandra and Harel. Indeed, we show that some combinations of features yield serious limitations, analogous to FOk definability in the relational context. On the other hand, the limitations come with benefits such as the existence of powerful nor- mal forms. Other languages are "almost" complete, but fall short because of subtle limitations reminiscent of the copy elimination problem in object databases.
Type de document :
Communication dans un congrès
ICDT, Mar 2012, Berlin, Germany. pp.46-60, 2012
Liste complète des métadonnées

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

Contributeur : Serge Abiteboul <>
Soumis le : vendredi 14 décembre 2012 - 18:03:36
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : vendredi 15 mars 2013 - 03:52:39


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00765558, version 1



Serge Abiteboul, Pierre Bourhis, Victor Vianu. Highly expressive query languages for unordered data trees. ICDT, Mar 2012, Berlin, Germany. pp.46-60, 2012. 〈hal-00765558〉



Consultations de la notice


Téléchargements de fichiers