Simplifying XML schema: effortless handling of nondeterministic regular expressions

ABSTRACT

Whether beloved or despised, XML Schema is momentarily the only industrially accepted schema language for XML and is unlikely to become obsolete any time soon. Nevertheless, many nontransparent restrictions unnecessarily complicate the design of XSDs. For instance, complex content models in XML Schema are constrained by the infamous unique particle attribution (UPA) constraint. In formal language theoretic terms, this constraint restricts content models to deterministic regular expressions. As the latter constitute a semantic notion and no simple corresponding syntactical characterization is known, it is very difficult for non-expert users to understand exactly when and why content models do or do not violate UPA. In the present paper, we therefore investigate solutions to relieve users from the burden of UPA by automatically transforming nondeterministic expressions into concise deterministic ones defining the same language or constituting good approximations. The presented techniques facilitate XSD construction by reducing the design task at hand more towards the complexity of the modeling task. In addition, our algorithms can serve as a plug-in for any model management tool which supports export to XML Schema format.

REFERENCES

• 1: Helena Ahonen, Disambiguation of SGML Content Models, Proceedings of the Third International Workshop on Principles of Document Processing, p.27-37, September 23, 1996
• 2: Denilson Barbosa , Laurent Mignet , Pierangelo Veltri, Studying the XML Web: Gathering Statistics from an XML Sample, World Wide Web, v.8 n.4, p.413-438, December 2005 [doi>10.1007/s11280-005-1544-y]
• 3: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM (JACM), v.55 n.2, p.1-79, May 2008 [doi>10.1145/1346330.1346333]
• 4: P. A. Bernstein. Applying Model Management to Classical Meta Data Problems. In Conference on Innovative Data Systems Research (CIDR), 2003.
• 5: Geert Jan Bex , Frank Neven , Jan Van den Bussche, DTDs versus XML schema: a practical study, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017095]
• 6: Geert Jan Bex , Wouter Gelade , Frank Neven , Stijn Vansummeren, Learning deterministic regular expressions for the inference of schemas from XML data, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367609]
• 7: Geert Jan Bex , Frank Neven , Thomas Schwentick , Karl Tuyls, Inference of concise DTDs from XML data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: Geert Jan Bex , Frank Neven , Stijn Vansummeren, Inferring XML schema definitions from XML data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 9: Geert Jan Bex , Frank Neven , Stijn Vansummeren, SchemaScope: a system for inferring and cleaning XML schemas, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376750]
• 10: Anne Brüggemann-Klein , Derick Wood, One-unambiguous regular languages, Information and Computation, v.142 n.2, p.182-206, May 2, 1998 [doi>10.1006/inco.1997.2695]
• 11: Dunren Che , Karl Aberer , Tamer Özsu, Query optimization in XML structured-document databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.263-289, September 2006 [doi>10.1007/s00778-005-0172-6]
• 12: Cristiana Chitic , Daniela Rosu, On validation of XML streams using finite state machines, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017096]
• 13: Fang Du , Sihem Amer-Yahia , Juliana Freire, ShreX: managing XML documents in relational databases, Proceedings of the Thirtieth international conference on Very large data bases, p.1297-1300, August 31-September 03, 2004, Toronto, Canada
• 14: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 15: Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564713]
• 16: W. Gelade and F. Neven. Succinctness of the complement and intersection of regular expressions. In Symposium on Theoretical Aspects of Computer Science (STACS), p. 325--336, 2008.
• 17: G. Ghelli, D. Colazzo, C. Sartiani. Efficient inclusion for a class of xml types with interleaving and counting. In Database Programming Languages (DBPL), p. 231--245, 2007.
• 18: Giorgio Ghelli , Dario Colazzo , Carlo Sartiani, Linear time membership in a class of regular expressions with interleaving and counting, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458135]
• 19: H. Gruber and J. Johannsen. Optimal lower bounds on regular expression size using communication complexity. In Foundations of Software Science and Computation Structures (FOSSACS), p. 273--286, 2008.
• 20: Pekka Kilpeläinen , Rauno Tuhkanen, One-unambiguity of regular expressions with numeric occurrence indicators, Information and Computation, v.205 n.6, p.890-916, June, 2007 [doi>10.1016/j.ic.2006.12.003]
• 21: Christoph Koch , Stefanie Scherzinger, Attribute grammars for scalable query processing on XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.3, p.317-342, July 2007 [doi>10.1007/s00778-005-0169-1]
• 22: Christoph Koch , Stefanie Scherzinger , Nicole Schweikardt , Bernhard Stegmaier, Schema-based scheduling of event processors and buffer minimization for queries on structured data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.228-239, August 31-September 03, 2004, Toronto, Canada
• 23: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 24: W. Martens, F. Neven, and T. Schwentick. Complexity of decision problems for simple regular expressions. In Mathematical Foundations of Computer Science (MFCS), p. 889--900, 2004.
• 25: Wim Martens , Frank Neven , Thomas Schwentick , Geert Jan Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems (TODS), v.31 n.3, p.770-813, September 2006 [doi>10.1145/1166074.1166076]
• 26: Laurent Mignet , Denilson Barbosa , Pierangelo Veltri, The XML web: a first study, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775223]
• 27: F. Neven and T. Schwentick. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science, 2(3), 2006.
• 28: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 29: Arto Salomaa, Two Complete Axiom Systems for the Algebra of Regular Events, Journal of the ACM (JACM), v.13 n.1, p.158-169, Jan. 1966 [doi>10.1145/321312.321326]
• 30: H.S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema part 1: Structures. World Wide Web Consortium (W3C), May 2001.
• 31: Eric van der Vlist, XML Schema, O'Reilly Media, Inc., 2002
• 32: P. van Emde Boas. The convenience of tilings. In Complexity, Logic and Recursion Theory, p. 331--363.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

General Terms:
Algorithms, Languages, Theory

Keywords:
deterministic regular expressions, upa, xml schema