Distributed XML design

DOI10.1016/J.JCSS.2011.02.003zbMATH Open1246.68066arXiv1012.2648OpenAlexW4206399782WikidataQ59259518 ScholiaQ59259518MaRDI QIDQ657904FDOQ657904

Georg Gottlob, M. Manna, Serge Abiteboul

Publication date: 11 January 2012

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

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.

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

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

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)

Cites Work

• State complexity of regular languages
• Deciding Equivalence of Finite Tree Automata
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Problems complete for deterministic logarithmic space
• Title not available (Why is that?)
• On the minimization of XML schemas and tree automata for unranked trees
• Title not available (Why is that?)
• Minimal NFA Problems are Hard
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• Title not available (Why is that?)
• Constructions for alternating finite automata^∗
• One-unambiguous regular languages
• Space-bounded reducibility among combinatorial problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Translating regular expressions into small ε-free nondeterministic finite automata
• Mathematical Foundations of Computer Science 2004
• Distributed XML design

Cited In (2)

• Distributed XML design
• A Typed Calculus for Querying Distributed XML Documents

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)