Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
Authors:
- Wouter GeladeWGWouter Gelade
- Wim MartensWMWim Martens
- Frank NevenFNFrank Neven
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (5) , 2021-2043
Abstract
The presence of a schema offers many advantages in processing, translating, querying, and storage of XML data. Basic decision problems such as equivalence, inclusion, and nonemptiness of intersection of schemas form the basic building blocks for schema optimization and integration, and algorithms for static analysis of transformations. It is thereby paramount to establish the exact complexity of these problems. Most common schema languages for XML can be adequately modeled by some kind of grammar with regular expressions at right-hand sides. In this paper, we observe that, apart from the usual regular operators of union, concatenation, and Kleene-star, schema languages also allow numerical occurrence constraints and interleaving operators. Although the expressiveness of these operators remains within the regular languages, the presence or absence of these operators has a significant impact on the complexity of the basic decision problems. We present a complete overview of the complexity of the basic decision problems for DTDs, XSDs, and Relax NG with regular expressions incorporating numerical occurrence constraints and interleaving. We also discuss chain regular expressions and the complexity of the schema simplification problem incorporating the new operators.Keywords
This publication has 28 references indexed in Scilit:
- XPath satisfiability in the presence of DTDsJournal of the ACM, 2008
- On the minimization of XML Schemas and tree automata for unranked treesJournal of Computer and System Sciences, 2007
- One-unambiguity of regular expressions with numeric occurrence indicatorsInformation and Computation, 2007
- Frontiers of tractability for typechecking simple XML transformationsJournal of Computer and System Sciences, 2007
- Expressiveness and complexity of XML SchemaACM Transactions on Database Systems, 2006
- XDuceACM Transactions on Internet Technology, 2003
- Shuffle languages are in PTheoretical Computer Science, 2001
- One-Unambiguous Regular LanguagesInformation and Computation, 1998
- The Complexity of Word Problems - This Time with InterleavingInformation and Computation, 1994
- AlternationJournal of the ACM, 1981