Skip to Main content Skip to Navigation
Conference papers

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], Inria Saclay - Ile de France
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Alban Galland Connect in order to contact the contributor
Submitted on : Tuesday, November 3, 2009 - 3:59:52 PM
Last modification on : Thursday, April 7, 2022 - 3:09:02 AM
Long-term archiving on: : Thursday, June 17, 2010 - 7:13:11 PM


Files produced by the author(s)



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



Record views


Files downloads