Distributed XML Design

Serge Abiteboul 1 Georg Gottlob 2 Marco Manna 3
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 : 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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00429591
Contributor : Alban Galland <>
Submitted on : Tuesday, November 3, 2009 - 3:59:52 PM
Last modification on : Thursday, February 7, 2019 - 5:29:34 PM
Long-term archiving on : Thursday, June 17, 2010 - 7:13:11 PM

File

p247-abiteboul.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

382

Files downloads

212