Distributed XML Design

Serge Abiteboul 1 Georg Gottlob 2 Marco Manna 3
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 : A distributed XML document is an XML document that spans several machines or Web repositories. We assume that a distribution design of the document tree is given, providing an XML tree some of whose leaves are "docking points", to which XML subtrees can be attached. These subtrees may be provided and controlled by peers at remote locations, or may correspond to the result of function calls, e.g., Web services. If a global type τ, e.g. a DTD, is specified for a distributed document T, it would be most desirable to be able to break this type into a collection of local types, called a local typing, such that the document satisfies τ if and only if each peer (or function) satisfies its local type. In this paper we lay out the fundamentals of a theory of local typing and provide formal definitions of three main variants of locality: local typing, maximal local typing, and perfect typing, the latter being the most desirable. We study the following relevant decision problems: (i) given a typing for a design, determine whether it is local, maximal local, or perfect; (ii) given a design, establish whether a (maximal) local, or perfect typing does exist. For some of these problems we provide tight complexity bounds (polynomial space), while for the others we show exponential upper bounds. A main contribution is a polynomial-space algorithm for computing a perfect typing in this context, if it exists.
Type de document :
Communication dans un congrès
Symposium on Principles of Database Systems (PODS), Jun 2009, Providence, United States. 2009, 〈10.1145/1559795.1559833〉
Liste complète des métadonnées

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

Contributeur : Alban Galland <>
Soumis le : mardi 3 novembre 2009 - 15:59:52
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:13:11


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




Serge Abiteboul, Georg Gottlob, Marco Manna. Distributed XML Design. Symposium on Principles of Database Systems (PODS), Jun 2009, Providence, United States. 2009, 〈10.1145/1559795.1559833〉. 〈inria-00429591〉



Consultations de la notice


Téléchargements de fichiers