On the equivalence of distributed systems with queries and communication

Serge Abiteboul 1, 2 Yannis Katsis 3 Balder Ten Cate 4
2 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 : Distributed data management systems consist of peers that store, exchange and process data in order to collaboratively achieve a common goal, such as evaluating some query. We study the equivalence of such systems. We model a distributed system by a collection of Active XML documents, i.e., trees augmented with function calls for performing tasks such as sending, receiving and querying data. As our model is quite general, the equivalence problem turns out to be undecidable. However, we exhibit several restrictions of the model, for which equivalence can be effectively decided. We also study the computational complexity of the equivalence problem, and present an axiomatization of equivalence, in the form of a set of equivalence-preserving rewrite rules allowing us to optimize a system by rewriting it into an equivalent, but possibly more efficient system.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00879029
Contributeur : Serge Abiteboul <>
Soumis le : jeudi 31 octobre 2013 - 15:31:48
Dernière modification le : jeudi 9 février 2017 - 15:47:30
Document(s) archivé(s) le : samedi 1 février 2014 - 04:28:57

Fichier

axml-equiv.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00879029, version 1

Collections

Citation

Serge Abiteboul, Yannis Katsis, Balder Ten Cate. On the equivalence of distributed systems with queries and communication. Journal of Computer and System Sciences, Elsevier, 2013. 〈hal-00879029〉

Partager

Métriques

Consultations de
la notice

402

Téléchargements du document

102