On the equivalence of distributed systems with queries and communication - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2013

On the equivalence of distributed systems with queries and communication

Résumé

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.
Fichier principal
Vignette du fichier
axml-equiv.pdf (687.37 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00879029 , version 1 (31-10-2013)

Identifiants

  • HAL Id : hal-00879029 , version 1

Citer

Serge Abiteboul, Yannis Katsis, Balder Ten Cate. On the equivalence of distributed systems with queries and communication. Journal of Computer and System Sciences, 2013. ⟨hal-00879029⟩
257 Consultations
126 Téléchargements

Partager

Gmail Facebook X LinkedIn More