Abstract
It is shown that the class of regular tree languages admitting one-pass preorder typing is exactly the class defined by restrained competition tree grammars introduced by Murata et al. [14]. In a streaming context, the former is the largest class of XSDs where every element in a document can be typed when its opening tag is met. The main technical machinery consists of semantical characterizations of restrained competition grammars and their subclasses. In particular, they can be characterized in terms of the context of nodes, closure properties, allowed patterns and guarded DTDs. It is further shown that deciding whether a schema is restrained competition is tractable. Deciding whether a schema is equivalent to a restrained competition tree grammar, or one of its subclasses, is much more difficult: it is complete for EXPTIME. We show that our semantical characterizations allow for easy optimization and minimization algorithms. Finally, we relate the notion of one-pass preorder typing to the existing XML Schema standard.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: STOC 2004, pp. 202–211 (2004)
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: Version 1, April 3, 2001. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)
Brüggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Information and Computation 142(2), 182–206 (1998)
World Wide Web Consortium. Extensible Markup Language (XML), http://www.w3.org/XML
World Wide Web Consortium. XML Schema, http://www.w3.org/XML/Schema
World Wide Web Consortium. XML Schema Part 0: Primer, http://www.w3.org/TR/xmlschema-0/
World Wide Web Consortium. XML Schema Part 1: Structures, http://www.w3.org/TR/xmlschema-1/
Hosoya, H., Pierce, B.C.: XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology (TOIT) 3(2), 117–148 (2003)
Koch, C., Scherzinger, S.: Attribute grammars for scalable query processing on XML streams. In: DBPL, pp. 233–256 (2003)
Mani, M.: Keeping chess alive - Do we need 1-unambiguous content models? In: Extreme Markup Languages, Montreal, Canada (2001)
Martens, W., Neven, F.: Typechecking top-down uniform unranked tree transducers. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 64–78. Springer, Heidelberg (2002)
Martens, W., Neven, F.: Frontiers of tractability for typechecking simple XML transformations. In: PODS 2004, pp. 23–34 (2004)
Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for simple regular expressions. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 889–900. Springer, Heidelberg (2004)
Murata, M., Lee, D., Mani, M.: Taxonomy of XML schema languages using formal language theory. In: Extreme Markup Languages, Montreal, Canada (2001)
Neven, F.: Automata, logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol. 2471, pp. 2–26. Springer, Heidelberg (2002)
Papakonstantinou, Y., Vianu, V.: DTD inference for views of XML data. In: PODS 2000, pp. 35–46. ACM Press, New York (2000)
Papakonstantinou, Y., Vianu, V.: Incremental validation of XML documents. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 47–63. Springer, Heidelberg (2002)
Segoufin, L., Vianu, V.: Validating streaming XML documents. In: PODS 2002, pp. 53–64. ACM Press, New York (2002)
Seidl, H.: Deciding equivalence of finite tree automata. SIAM Journal on Computing 19(3), 424–437 (1990)
Sperberg-McQueen, C.M.: XML Schema 1.0: A language for document grammars. In: XML 2003 - Conference Proceedings (2003)
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC 1973, pp. 1–9 (1973)
Suciu, D.: Typechecking for semistructured data. In: Ghelli, G., Grahne, G. (eds.) DBPL 2001. LNCS, vol. 2397, p. 1. Springer, Heidelberg (2001)
van der Vlist, E.: XML Schema. O’Reilly, Sebastopol (2002)
van der Vlist, E.: Relax NG. O’Reilly, Sebastopol (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Martens, W., Neven, F., Schwentick, T. (2004). Which XML Schemas Admit 1-Pass Preorder Typing?. In: Eiter, T., Libkin, L. (eds) Database Theory - ICDT 2005. ICDT 2005. Lecture Notes in Computer Science, vol 3363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30570-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-30570-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24288-8
Online ISBN: 978-3-540-30570-5
eBook Packages: Computer ScienceComputer Science (R0)