XML with data values: typechecking revisited

ABSTRACT

We investigate the type checking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the type checking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, type checking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The main contribution of the present paper is to trace a fairly tight boundary of decidability for type checking with data values. The complexity of type checking in the decidable cases is also considered.

REFERENCES

• 1: D. Beech, S. Lawrence, M. Maloney, N. Mendelsohn, and H. Thompson. XML schema part 1: Structures. May 1999. http://www.w3.org/TR/xmlschema-1/.
• 2: P. Biron and A. Malhotra. XML schema part 2: Datatypes. May 1999. http://www.w3.org/TR/xmlschema-2/.
• 3: A. Bruggemann-Klein, M. Murata, and D. Wood. Regular tree languages over non-ranked alphabets. Unpublished Manuscript, 1998.
• 4: J. R. B. uchi. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundl. Math., vol. 6, pp. 66-92, 1960.
• 5: A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. on Computing, 14(3):671-677, 1985.
• 6: Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
• 7: Vassilis Christophides , Sophie Cluet , Jérǒme Simèon, On wrapping query languages and efficient XML integration, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.141-152, May 15-18, 2000, Dallas, Texas, United States
• 8: J. Clark. XML path language (XPath), 1999. http://www.w3.org/TR/xpath.
• 9: J. Clark. XSL transformations (XSLT) specification, 1999. http://www.w3.org/TR/WD-xslt.
• 10: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 11: Alin Deutsch , Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for XML, Proceeding of the eighth international conference on World Wide Web, p.1155-1169, May 1999, Toronto, Canada
• 12: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, Second Edition, 1999.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: R.L. Graham, B.L. Rothschild and J. H. Spencer, Ramsey Theory (Second Edition). Wiley, New York, 1990.
• 15: H. Hosoya and B. C. Pierce. XDuce: An XML Processing Language. WebDB'2000 (Informal Proceedings).
• 16: Haruo Hosoya , Benjamin Pierce, Regular expression pattern matching for XML, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 2001, London, United Kingdom
• 17: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 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, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 20: John C. Mitchell, The implication problem for functional and inclusion dependencies, Information and Control, v.56 n.3, p.154-173, March 1983 [doi>10.1016/S0019-9958(83)80002-3]
• 21: F. Neven and T. Schwentick. XML Schemas without Order. Unpublished manuscript, 1999.
• 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: F. P. Ramsey, On a problem of formal logic. Proceedings of the London Mathematical Society, 30(2):264-286, 1929.
• 24: J. Robie. The design of XQL, 1999. http://www.texcel.no/whitepapers/xql-design.html.
• 25: Ron van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Journal of Computer and System Sciences, v.54 n.1, p.113-135, Feb. 1997 [doi>10.1006/jcss.1997.1455]
• 26: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Management, Theory, Verification