Schemas for unordered XML on a DIME
From MaRDI portal
Abstract: We investigate schema languages for unordered XML having no relative order among siblings. First, we propose unordered regular expressions (UREs), essentially regular expressions with unordered concatenation instead of standard concatenation, that define languages of unordered words to model the allowed content of a node (i.e., collections of the labels of children). However, unrestricted UREs are computationally too expensive as we show the intractability of two fundamental decision problems for UREs: membership of an unordered word to the language of a URE and containment of two UREs. Consequently, we propose a practical and tractable restriction of UREs, disjunctive interval multiplicity expressions (DIMEs). Next, we employ DIMEs to define languages of unordered trees and propose two schema languages: disjunctive interval multiplicity schema (DIMS), and its restriction, disjunction-free interval multiplicity schema (IMS). We study the complexity of the following static analysis problems: schema satisfiability, membership of a tree to the language of a schema, schema containment, as well as twig query satisfiability, implication, and containment in the presence of schema. Finally, we study the expressive power of the proposed schema languages and compare them with yardstick languages of unordered trees (FO, MSO, and Presburger constraints) and DTDs under commutative closure. Our results show that the proposed schema languages are capable of expressing many practical languages of unordered trees and enjoy desirable computational properties.
Recommendations
Cites work
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 2043533 (Why is no real title available?)
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- Almost-linear inclusion for XML regular expression types
- Complexity of decision problems for XML schemas and chain regular expressions
- Containment and equivalence for a fragment of XPath
- Counting in trees
- Deciding definability by deterministic regular expressions
- Efficient inclusion for a class of XML types with interleaving and counting
- Highly expressive query languages for unordered data trees
- Linear time membership in a class of regular expressions with counting, interleaving, and unordered concatenation
- Mathematical Foundations of Computer Science 2004
- Normal form algorithms for extended context-free grammars
- On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
- On the complexity of typechecking top-down XML transformations
- One-unambiguous regular languages
- Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
- Recognizing Shuffled Languages
- Schemas for unordered XML on a DIME
- TQL: a query language for semistructured data based on the ambient logic
- Term Rewriting and Applications
- The complexity of satisfiability problems
- The membership problem for regular expressions with unordered concatenation and numerical constraints
- Tree pattern query minimization
- Typechecking top-down XML transformations: Fixed input or output schemas
- Validity of tree pattern queries with respect to schema information
- XPath satisfiability in the presence of DTDs
Cited in
(5)
This page was built for publication: Schemas for unordered XML on a DIME
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905687)
