Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/1424
Title: | Expressiveness and complexity of XML Schema | Authors: | MARTENS, Wim NEVEN, Frank Schwentick, Thomas BEX, Geert Jan |
Issue Date: | 2006 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | ACM TRANSACTIONS ON DATABASE SYSTEMS, 31(3). p. 770-813 | Abstract: | The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical characterizations of the Element Declarations Consistent (EDC) rule are provided. In particular, it is obtained that schemas satisfying EDC can only reason about regular properties of ancestors of nodes. Hence, w.r.t. expressive power, XML Schema is closer to DTDs than to tree automata. These theoretical results are complemented with an investigation of the XML Schema Definitions (XSDs) occurring in practice, revealing that the extra expressiveness of XSDs over DTDs is only used to a very limited extent. As this might be due to the complexity of the XML Schema specification and the difficulty to understand the effect of constraints on typing and validation of schemas, a simpler formalism equivalent to XSDs is proposed. It is based on contextual patterns rather than on recursive types and it might serve as a light-weight front end for XML Schema. Next, the effect of EDC on the way XML documents can be typed is discussed. It is argued that a cleaner, more robust, larger but equally feasible class is obtained by replacing EDC with the notion of 1-pass preorder typing (1PPT): schemas that allow to determine the type of an element of a streaming document when its opening tag is met. This notion can be defined in terms of grammars with restrained competition regular expressions and there is again an equivalent syntactical formalism based on contextual patterns. Finally, algorithms for recognition, simplification, and inclusion of schemas for the various classes are given. | Keywords: | algorithms; design; languages; standardization; theory; XML; XML; Schema; validation; AUTOMATA | Document URI: | http://hdl.handle.net/1942/1424 | Link to publication/dataset: | http://doi.acm.org/10.1145/1166074.1166076 | ISSN: | 0362-5915 | e-ISSN: | 1557-4644 | ISI #: | 000241433500002 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2007 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tods.pdf | Peer-reviewed author version | 428.1 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
87
checked on Oct 14, 2024
Page view(s)
66
checked on Sep 7, 2022
Download(s)
186
checked on Sep 7, 2022
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.