More Web Proxy on the site http://driver.im/

Article

Expressiveness of XSDs: from practice to theory, there and back again

Authors:

Thomas SchwentickAuthors Info & Claims

WWW '05: Proceedings of the 14th international conference on World Wide Web

Pages 712 - 721

https://doi.org/10.1145/1060745.1060848

Published: 10 May 2005 Publication History

Abstract

On an abstract level, XML Schema increases the limited expressive power of Document Type Definitions (DTDs) by extending them with a recursive typing mechanism. However, an investigation of the XML Schema Definitions (XSDs) occurring in practice reveals that the vast majority of them are structurally equivalent to DTDs. 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. To shed some light on the actual expressive power of XSDs this paper studies the impact of the Element Declarations Consistent (EDC) and the Unique Particle Attribution (UPA) rule. An equivalent formalism based on contextual patterns rather than on recursive types is proposed which might serve as a light-weight front end for XML Schema. Finally, the effect of EDC and UPA on the way XML documents can be typed is discussed. It is argued that a cleaner, more robust, stronger but equally efficient class is obtained by replacing EDC and UPA with the notion of 1-pass preorder typing: 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 restrained competition regular expressions and there is again an equivalent syntactical formalism based on contextual patterns.

References

[1]

G.J. Bex, F. Neven and J. Van den Bussche. DTDs versus XML Schema: A Practical Study. In WebDB 2004, pages 79--84, 2004.

Digital Library

[2]

A. Brüggemann-Klein, M. Murata, and D. Wood. Regular tree and regular hedge languages over unranked alphabets. Hongkong Univ. of Sc. and Tech., 2001. Tech. Rep. HKUST-TCSC-2001-0.

[3]

A. Brüggemann-Klein and D. Wood. One-unambiguous regular languages. Information and Computation, 142(2):182--206, 1998.

Digital Library

[4]

J. Clark and M. Murata. RELAX NG Specification, 2001. http://www.oasis-open.org/committees/relax-ng/spec-20011203.html

[5]

E. Cerami. XML for Bioinformatics. Springer-Verlag, 2004.

Digital Library

[6]

R. Cover. The Cover Pages. http://xml.coverpages.org/

[7]

B. DuCharme. Filling in the DTD gaps with Schematron. O'Reilly xml.com, May 2002. http://www.xml.com/pub/a/2002/05/15/schematron.html

[8]

D. Fiorello, N. Gessa, P. Marinelli and F. Vitali. DTD++ 2.0: adding support for co-constraints. In Extreme Markup Languages 2004, Montreal, Canada.

[9]

R. Jelliffe. The current state of the art of schema languages for XML. Presentation at XML Asia Pacific, Sidney, Australia, 2001.

[10]

N. Klarlund, A. Moller, and M. I. Schwartzbach. The DSD schema language. Autom. Softw. Eng., 9(3):285--319, 2002.

Digital Library

[11]

D. Lee and W.W. Chu. Comparative analysis of six XML schema languages. ACM SIGMOD Record, 29(3), 2000.

Digital Library

[12]

M. Mani. Keeping chess alive - Do we need 1-unambiguous content models? In Extreme Markup Languages, Montreal, Canada, 2001.

[13]

W. Martens, F. Neven, and T. Schwentick. Which XML schemas admit 1-pass preorder typing? In ICDT 2005. To Appear.

Digital Library

[14]

M. Murata, D. Lee, and M. Mani. Taxonomy of XML schema languages using formal language theory. In Extreme Markup Languages, Montreal, Canada, 2001.

[15]

F. Neven. Automata theory for XML researchers. SIGMOD Record, 31(3):39--46, 2002.

Digital Library

[16]

Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In PODS 2000, pages 35--46, 2000.

Digital Library

[17]

C. Sacerdoti Coen, P. Marinelli, and F. Vitali. Schemapath, a minimal extension to XML Schema for conditional constraints. In WWW 2004, pages 164--174, 2004.

Digital Library

[18]

A. Sahuguet. Everything You Ever Wanted to Know About DTDs, But Were Afraid to Ask. In WebDB 2000, pages 69--74, 2000.

Digital Library

[19]

Schematron. http://xml.ascc.net/schematron/

[20]

T. Schwentick. XPath query containment. SIGMOD Record, 33(1):101--109, 2004.

Digital Library

[21]

L. Segoufin and V. Vianu. Validating streaming XML documents. In PODS 2002, pages 53--64, 2002.

Digital Library

[22]

J. Siméon and P. Wadler. The essence of XML. In POPL 2003, pages 1--13, 2003.

Digital Library

[23]

E. van der Vlist. XML Schema. O'Reilly, 2002.

Digital Library

[24]

F. Vitali, N. Amorosi and N. Gessa. Datatype- and namespace-aware DTDs: a minimal extension. In Extreme Markup Languages 2003, Montreal, Canada.

[25]

World Wide~Web Consortium. Extensible Markup Language (XML). http://www.w3.org/XML

[26]

World Wide Web Consortium. XML Schema Part 1: Structures. http://www.w3.org/TR/xmlschema-1/

[27]

World Wide Web Consortium. XML Schema Part 2: Datatypes. http://www.w3.org/TR/xmlschema-2/

[28]

World Wide Web Consortium. Datatypes for DTDs (DT4DTD) 1.0 http://www.w3.org/TR/dt4dtd

[29]

XML-dev, Monthly archives. http://lists.xml.org/archives/xml-dev/200102/msg00008.html

[30]

XML Schema Quality Checker. http://www.alphaworks.ibm.com/tech/xmlsqc

[31]

XQuery 1.0 and XPath 2.0 Data Model. http://www.w3.org/TR/xpath-datamodel/

Cited By

Wang XChen H(2020)Inferring Deterministic Regular Expression with UnorderSOFSEM 2020: Theory and Practice of Computer Science10.1007/978-3-030-38919-2_27(325-337)Online publication date: 17-Jan-2020
https://doi.org/10.1007/978-3-030-38919-2_27
Martens WTrautner T(2019)Dichotomies for Evaluating Simple Regular Path QueriesACM Transactions on Database Systems10.1145/333144644:4(1-46)Online publication date: 15-Oct-2019
https://dl.acm.org/doi/10.1145/3331446
Schwentick T(2019)Automata for XML---A surveyJournal of Computer and System Sciences10.1016/j.jcss.2006.10.00373:3(289-315)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.jcss.2006.10.003
Show More Cited By

Index Terms

Expressiveness of XSDs: from practice to theory, there and back again
1. Applied computing
  1. Document management and text processing
    1. Document preparation
      1. Hypertext / hypermedia creation
      2. Markup languages
2. Information systems
  1. World Wide Web
    1. Web data description languages
      1. Markup languages

Recommendations

Expressiveness and complexity of XML Schema

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 ...
Towards inference of more realistic XSDs
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

The XML has undoubtedly become a standard for data representation and manipulation. But most of XML documents are still created without the respective description of their structure, i.e. an XML schema. Hence, in this paper we focus on the problem of ...
Conceptual modeling of XML schemas
WIDM '03: Proceedings of the 5th ACM international workshop on Web information and data management

XML has become the standard format for representing structured and semi-structured data on the Web. To describe the structure and content of XML data, several XML schema languages have been proposed. Although being very useful for validating XML ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '05: Proceedings of the 14th international conference on World Wide Web

May 2005

781 pages

ISBN:1595930469

DOI:10.1145/1060745

Conference Chairs:
Allan Ellis
Southern Cross University
,
Tatsuya Hagino
Keio University

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
667
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XChen H(2020)Inferring Deterministic Regular Expression with UnorderSOFSEM 2020: Theory and Practice of Computer Science10.1007/978-3-030-38919-2_27(325-337)Online publication date: 17-Jan-2020
https://doi.org/10.1007/978-3-030-38919-2_27
Martens WTrautner T(2019)Dichotomies for Evaluating Simple Regular Path QueriesACM Transactions on Database Systems10.1145/333144644:4(1-46)Online publication date: 15-Oct-2019
https://dl.acm.org/doi/10.1145/3331446
Schwentick T(2019)Automata for XML---A surveyJournal of Computer and System Sciences10.1016/j.jcss.2006.10.00373:3(289-315)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.jcss.2006.10.003
Wang XChen H(2019)Learning Restricted Deterministic Regular Expressions with CountingWeb Information Systems Engineering – WISE 201910.1007/978-3-030-34223-4_7(98-114)Online publication date: 29-Oct-2019
https://doi.org/10.1007/978-3-030-34223-4_7
Wang XChen H(2019)Learning a Subclass of Deterministic Regular Expression with CountingKnowledge Science, Engineering and Management10.1007/978-3-030-29551-6_29(341-348)Online publication date: 21-Aug-2019
https://doi.org/10.1007/978-3-030-29551-6_29
Chen HLi YDong CChu XMou XMin W(2019)A Large-Scale Repository of Deterministic Regular Expression Patterns and Its ApplicationsAdvances in Knowledge Discovery and Data Mining10.1007/978-3-030-16142-2_20(249-261)Online publication date: 20-Mar-2019
https://doi.org/10.1007/978-3-030-16142-2_20
Li YChu XMou XDong CChen HDesai BFlesca SZumpano EMasciari ECaroprese L(2018)Practical Study of Deterministic Regular Expressions from Large-scale XML and Schema DataProceedings of the 22nd International Database Engineering & Applications Symposium10.1145/3216122.3216126(45-53)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3216122.3216126
Grijzenhout SMarx M(2018)The quality of the XML WebWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2012.12.00119(59-68)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.1016/j.websem.2012.12.001
Wang XChen H(2018)Inferring Deterministic Regular Expression with CountingConceptual Modeling10.1007/978-3-030-00847-5_15(184-199)Online publication date: 26-Sep-2018
https://doi.org/10.1007/978-3-030-00847-5_15
Martens WNeven FNiewerth MSchwentick T(2017)BonXaiACM Transactions on Database Systems10.1145/310596042:3(1-42)Online publication date: 24-Aug-2017
https://dl.acm.org/doi/10.1145/3105960
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents