Abstract
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as output schemas. The complexity of the typechecking problems in this scenario range from PTIME to EXP- TIME.
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
N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. Typechecking XML views of relational databases. In Proc. 16th IEEE Symposium on Logic in Computer Science (LICS 2001), pages 421–130, 2001.
N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. XML with data values: Typechecking revisited. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 560–572, 2001.
G. J. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. Information Systems, 27(1):21–39, 2002.
A. Brüggemann-Klein, M. Murata, and D. Wood. 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.
P. Buneman, M. Fernandez, and D. Suciu. UnQl: a query language and algebra for semistructured data based on structural recursion. The VLDB Journal, 9(1):76–110, 2000.
James Clark. XSL transformations version 1.0. http://www.w3.org/TR/WD-xslt, august 1999.
World Wide Web Consortium. XML Schema. http://www.w3.org/XML/Schema.
S. A. Cook. An observation on time-storage trade-off. Journal of Computer and System Sciences, 9(3):308–316, 1974.
J. Engelfriet and H. Vogler. Macro tree transducers. Journal of Computer and System Sciences, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
F. Gécseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1–68. Springer, 1997.
R. E. Ladner, R. J. Lipton, and L. J. Stockmeyer. Alternating pushdown and stack automata. SIAM Journal on Computing, 13(1):135–155, 1984.
S. Maneth and F. Neven. Structured document transformations based on XSL. In R. Connor and A. Mendelzon, editors, Research Issues in Structured and Semistructured Database Programming (DBPL’99), volume 1949 of Lecture Notes in Computer Science, pages 79–96. Springer, 2000.
T. Milo and D. Suciu. Type inference for queries on semistructured data. In Proceedings of the Eighteenth ACM Symposium on Principles of Database Systems, pages 215–226. ACM Press, 1999.
T. Milo, D. Suciu, and V. Vianu. Type checking for XML transformers. In Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems, pages 11–22. ACM Press, 2000.
F. Neven. Automata theory for XML researchers. SIGMOD Record, 31(3), 2002.
F. Neven and T. Schwentick. XML schemas without order. Unpublished manuscript, 1999.
F. Neven and T. Schwentick. Query automata on finite trees. Theoretical Computer Science, 275:633–674, 2002.
Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In Proc. 20th Symposium on Principles of Database Systems (PODS 2001), pages 35–46. ACM Press, 2001.
H. Seidl. Deciding equivalence of finite tree automata. SIAM Journal on Computing, 19(3):424–437, 1990.
H. Seidl. Haskell overloading is DEXPTIME-complete. Information Processing Letters, 52(2):57–60, 1994.
L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 1–9, Austin, Texas, 30 April–2 May 1973.
D. Suciu. Typechecking for semistructured data. In Proceedings of the 8th Workshop on Data Bases and Programming Languages (DBPL 2001), 2001.
D. Suciu. The XML typechecking problem. SIGMOD Record, 31(1):89–96, 2002.
A. Tozawa. Towards static type checking for XSLT. In Proceedings of ACM Symposium on Document Engineering, 2001.
M. Y. Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30:261–264, March 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Martens, W., Neven, F. (2003). Typechecking Top-Down Uniform Unranked Tree Transducers. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds) Database Theory — ICDT 2003. ICDT 2003. Lecture Notes in Computer Science, vol 2572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36285-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-36285-1_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00323-6
Online ISBN: 978-3-540-36285-2
eBook Packages: Springer Book Archive