Frontiers of tractability for typechecking simple XML transformations

ABSTRACT

Typechecking consists of statically verifying whether the output of an XML transformation is always conform to an output type for documents satisfying a given input type. We focus on complete algorithms which always produce the correct answer. We consider top-down XML transformations incorporating XPath expressions and abstract document types by grammars and tree automata. By restricting schema languages and transformations, we identify several practical settings for which typechecking is in polynomial time. Moreover, the resulting framework provides a rather complete picture as we show that most scenarios can not be enlarged without rendering the typechecking problem intractable. So, the present research sheds light on when to use fast complete algorithms and when to reside to sound but incomplete ones.

REFERENCES

• 1: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, Typechecking XML views of relational databases, ACM Transactions on Computational Logic (TOCL), v.4 n.3, p.315-354, July 2003 [doi>10.1145/772062.772065]
• 2: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, XML with data values: typechecking revisited, Journal of Computer and System Sciences, v.66 n.4, p.688-727, 1 June 2003 [doi>10.1016/S0022-0000(03)00032-1]
• 3: Geert Jan Bex , Sebastian Maneth , Frank Neven, A formal model for an expressive fragment of XSLT, Information Systems, v.27 n.1, p.21-39, March 2002 [doi>10.1016/S0306-4379(01)00033-3]
• 4: 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.
• 5: Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000 [doi>10.1007/s007780050084]
• 6: J. Clark and S. DeRose. XML Path Language (XPath). http://www.w3.org/TR/xpath.
• 7: Bogdan S Chlebus, Domino-tiling games, Journal of Computer and System Sciences, v.32 n.3, p.374-392, June 1986 [doi>10.1016/0022-0000(86)90036-X]
• 8: Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
• 9: Ferenc Gécseg , Magnus Steinby, Tree languages, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 10: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 11: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 12: J. Engelfriet and S. Maneth. A comparison of pebble tree transducers with macro tree transducers. Acta Information, 39:613--698, 2003.
• 13: D. Lee, M. Mani, and M. Murata. Reasoning about XML schema languages using formal language theory. Technical report, IBM Almaden Research Center, 2000. Log# 95071.
• 14: Sebastian Maneth , Frank Neven, Structured Document Transformations Based on XSL, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.80-98, September 01-03, 1999
• 15: W. Martens and F. Neven. Frontiers of tractability for typechecking simple XML transformations: Full version. http://alpha.luc.ac.be/~lucp1436/pubs.html.
• 16: Wim Martens , Frank Neven, Typechecking Top-Down Uniform Unranked Tree Transducers, Proceedings of the 9th International Conference on Database Theory, p.64-78, January 08-10, 2003
• 17: W. Martens, F. Neven, and T. Schwentick. Complexity of Simple Regular Expressions with Applications to XML Schema Languages. Submitted.
• 18: Tova Milo , Dan Suciu, Type inference for queries on semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303998]
• 19: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, v.66 n.1, p.66-97, 01 February 2003 [doi>10.1016/S0022-0000(02)00030-2]
• 20: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]
• 21: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 22: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 23: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 24: Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
• 25: Dan Suciu, The XML typechecking problem, ACM SIGMOD Record, v.31 n.1, March 2002 [doi>10.1145/507338.507360]
• 26: Akihiko Tozawa, Towards static type checking for XSLT, Proceedings of the 2001 ACM Symposium on Document engineering, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502187.502191]
• 27: Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003
• 28: World Wide Web Consortium. XML Schema. http://www.w3.org/XML/Schema.