Distributed XML design (Q657904)

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.