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

zbMATH Keywords

database designdistributed dataXML dataXML schemes

Mathematics Subject Classification ID

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

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.

Recommendations

• XML with data values: Typechecking revisited.
• On the complexity of typechecking top-down XML transformations
• The complexity of XPath query evaluation and XML typing
• A Typed Calculus for Querying Distributed XML Documents
• Frontiers of tractability for typechecking simple XML transformations

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1222566 (Why is no real title available?)
• scientific article; zbMATH DE number 1982638 (Why is no real title available?)
• scientific article; zbMATH DE number 2050057 (Why is no real title available?)
• scientific article; zbMATH DE number 2241906 (Why is no real title available?)
• Complexity of decision problems for XML schemas and chain regular expressions
• Constructions for alternating finite automata^∗
• Deciding Equivalence of Finite Tree Automata
• Distributed XML design
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• Mathematical Foundations of Computer Science 2004
• Minimal NFA Problems are Hard
• On the minimization of XML schemas and tree automata for unranked trees
• One-unambiguous regular languages
• Problems complete for deterministic logarithmic space
• Space-bounded reducibility among combinatorial problems
• State complexity of regular languages
• Translating regular expressions into small \(\epsilon \)-free nondeterministic finite automata

Cited in

(3)

• Distributed XML processing: theory and applications
• A Typed Calculus for Querying Distributed XML Documents
• Distributed XML design

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)