Document Server@UHasselt >
Research >
Research publications >

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
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.
URI: http://hdl.handle.net/1942/1424
Link to publication: http://doi.acm.org/10.1145/1166074.1166076
ISI #: 000241433500002
ISSN: 0362-5915
Category: A1
Type: Journal Contribution
Validation: ecoom, 2007
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Postprint428.1 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.