On the Equivalence of Distributed Systems with Queries and Communication

Serge Abiteboul 1 Balder ten Cate 2 Yannis Katsis 1
1 DAHU - Verification in databases
CNRS - Centre National de la Recherche Scientifique : UMR8643, Inria Saclay - Ile de France, ENS Cachan - École normale supérieure - Cachan, LSV - Laboratoire Spécification et Vérification [Cachan]
Abstract : Distributed data management systems consist of peers that store, exchange and process data in order to collaboratively achieve a common goal, such as evaluate 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00540199
Contributor : Yannis Katsis <>
Submitted on : Saturday, April 23, 2011 - 8:16:28 PM
Last modification on : Thursday, February 7, 2019 - 5:29:24 PM
Long-term archiving on : Thursday, November 8, 2012 - 5:15:23 PM

File

axml-equiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00540199, version 1

Collections

Citation

Serge Abiteboul, Balder ten Cate, Yannis Katsis. On the Equivalence of Distributed Systems with Queries and Communication. International Conference on Database Theory, Mar 2011, Uppsala, Sweden. ⟨inria-00540199⟩

Share

Metrics

Record views

375

Files downloads

291