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: 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 SizeFormat 
tods.pdfPostprint428.1 kBAdobe PDFView/Open
Show full item record

WEB OF SCIENCETM
Citations

82
checked on May 22, 2022

Page view(s)

48
checked on May 26, 2022

Download(s)

158
checked on May 26, 2022

Google ScholarTM

Check


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