# Highly Expressive Query Languages for Unordered Data Trees

Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
3 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 extensions 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 basic queries, the embedding of computation into data (as in Active XML), and the use of deterministic vs. nondeterministic 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 FO-k definability in the relational context. On the other hand, the limitations come with benefits such as the existence of powerful normal forms providing opportunities for optimization. Other languages are almost'' complete, but fall short because of subtle limitations reminiscent of the copy elimination problem in object databases.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2015, pp.30
Domaine :

https://hal.inria.fr/hal-01167068
Contributeur : Victor Vianu <>
Soumis le : mercredi 24 juin 2015 - 13:35:08
Dernière modification le : mardi 3 juillet 2018 - 11:44:26
Document(s) archivé(s) le : mardi 15 septembre 2015 - 22:10:12

### Fichier

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

### Identifiants

• HAL Id : hal-01167068, version 1

### Citation

Serge Abiteboul, Pierre Bourhis, Victor Vianu. Highly Expressive Query Languages for Unordered Data Trees. Theory of Computing Systems, Springer Verlag, 2015, pp.30. 〈hal-01167068〉

### Métriques

Consultations de la notice

## 467

Téléchargements de fichiers