Distributed XML design

DOI10.1016/J.JCSS.2011.02.003MaRDI QIDQ657904zbMATH OpenOpenAlexWikidataFDO

Authors Serge Abiteboul, Georg Gottlob, M. Manna

Publication date 11 January 2012

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.2648

database design distributed data XML data XML schemes

Internet topics (68M11) Distributed systems (68M14) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A distributed XML document is an XML document that spans several machines. We assume that a distribution design of the document tree is given, consisting of an XML kernel-document T[f1,...,fn] where some leaves are "docking points" for external resources providing XML subtrees (f1,...,fn, standing, e.g., for Web services or peers at remote locations). The top-down design problem consists in, given a type (a schema document that may vary from a DTD to a tree automaton) for the distributed document, "propagating" locally this type into a collection of types, that we call typing, while preserving desirable properties. We also consider the bottom-up design which consists in, given a type for each external resource, exhibiting a global type that is enforced by the local types, again with natural desirable properties. In the article, we lay out the fundamentals of a theory of distributed XML design, analyze problems concerning typing issues in this setting, and study their complexity.

Review text

The paper concerns distributed XML documents, i.e. XML documents stored in several machines. Assuming a distributed XML document \(T\), one of its parts, an XML kernel-document, is stored at some site, some of which leaves refer to external resources, which contain the rest of \(T\). To design such a distributed document means to specify types in an XML schema language, i.e. a global type in top-down-design or types for resources \(f_i\) in bottom-up design. Both strategies generate specific problems. In the case of the bottom-up design, we are interested in the global type \(\tau\) that results from each local source enforcing its local type \(\tau_i\). There is the question whether it is possible to describe such typing by a specific type language. In the top-down case one would like the extension of \(T\) to satisfy \(\tau\). The issue is to break down \(\tau\) into local types \(\tau_i\) that could be enforced locally. More precisely, the authors would like to provide each \(f_i\) with a typing \(\tau_i\), guaranteeing that (i) if each \(f_i\) verifies its type, then the global type is verified (soundness), and (ii) the typing \(\tau_1,\dots,\tau_n\) is not more restrictive than the global type (completeness). Such typing is called a local typing. The authors emphasize that their results depend on the choice of a typing language \(S\). They consider DTDs, XML Schema, and regular tree grammars and talk about \(S\)-typing. Section 2 fixes some preliminary notation, formally introduces the notions of type (according to several typing languages), distributed XML document, and defines the decision problems studied. Besides the local typing notions like maximal and perfect typing are introduced. For a given XML schema language \(S\), some verification problems are studied, e.g.: \(\bullet\) given an \(S\)-typing for a top-down \(S\)-design, determine whether the former is local, maximal local, or perfect; \(\bullet\) given a top-down \(S\)-design, establish whether a local, maximal local, or perfect \(S\)-typing does exist; \(\bullet\) given a bottom-up \(S\)-design, establish whether it defines an \(S\)-type. Regarding each of the problems important properties like decidability, PSPACE-completeness are EXPTIME-completeness are proved. Section 3 and Section 4 consider these problems in the context of the bottom-up and top-down design, respectively, presenting some basic results. Sections 5 and 6 give the main results for typing problems in the word case. Particularly, Section 6 presents the construction of the perfect automation for a design word problem. Section 7 completes the complexity analysis for trees. A new proof based on perfect automata is presented here. Section 8 concludes and mentions possible areas for further research. The paper is written on a very high formal level and it contains a lot of various and useful theoretical results for designing distributed XML data.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

Relax NG

This page was built for publication: Distributed XML design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657904)