Types for path correctness of XML queries

ABSTRACT

If a subexpression in a query will never contribute data to the query answer, this should be regarded as an error. This principle has been recently accepted into mainstream XML query languages, but was still waiting for a complete treatment. We provide here a precise definition for this class of errors, and define a type system that is sound and complete, in its search for such errors, for a core language, under mild restrictions on the use of recursion in type definitions. In the process, we describe a dichotomy among existential and universal type systems, which is useful to understand some unusual features of our type system.

REFERENCES

• 1: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel Query Language for Semistuctured Data. Journal of Digital Libraries, 1(1), pages 68--88, April 1997.
• 2: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, Typechecking XML Views of Relational Databases, Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, p.421, June 16-19, 2001
• 3: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, XML with data values: typechecking revisited, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-149, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375570]
• 4: 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
• 5: V. Benzaken, G. Castagna, and C. Miachon. CQL: a Pattern-based Query Language for XML. In Proceedings of 20th Bases de Données Avancées (BDA) (2004), 2004.
• 6: S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML Query Language. Technical report, World Wide Web Consortium, May 2003. W3C Working Draft.
• 7: Peter Buneman , Susan B. Davidson , Dan Suciu, Programming Constructs for Unstructured Data, Proceedings of the Fifth International Workshop on Database Programming Languages, p.12, September 06-08, 1995
• 8: D. Chamberlin, P. Fankhauser, D. Florescu, M. Marchiori, and J. Robie. XML Query Use Cases. Technical report, World Wide Web Consortium, Nov 2003. W3C Working Draft.
• 9: D. Colazzo. Path Correctness for XML Queries: Characterization and Static Type Checking. PhD thesis, Dipartimento di Informatica, Università di Pisa, 2004.
• 10: D. Colazzo, G. Ghelli, P. Manghi, and C. Sartiani. Types For Correctness of Queries Over Semistructured Data. In Proceedings of the Fifth International Workshop on the Web and Databases (WebDB 2002), Madison, Wisconsin, June 6-7, 2002, 2002.
• 11: H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata, 1997. release October, 1rst 2002.
• 12: D. Draper, P. Fankhauser, M. Fernandez, A. Malhotra, K. Rose, M. Rys, J. Siméon, and P. Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. Technical report, World Wide Web Consortium, Aug. 2003. W3C Working Draft.
• 13: Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for a Web-site management system, ACM SIGMOD Record, v.26 n.3, p.4-11, Sept. 1997 [doi>10.1145/262762.262763]
• 14: H. Hosoya and B. C. Pierce. XDuce: An XML Processing Language, 1999. Preliminary Report.
• 15: D. Lee, M. Mani, and M. Murata. Reasoning about XML Schema Languages using Formal Language Theory. Technical report, IBM Almaden Research, 2000. Technical Report -IBM Almaden Research.
• 16: 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]
• 17: H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1: Structures. Technical report, World Wide Web Consortium, May 2002. W3C Recommendation.
• 18: F. Yergeau, T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler. Extensible Markup Language (XML) 1.0 (Third Edition). Technical report, World Wide Web Consortium, Feb 2004. W3C Recommendation.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Theory, Verification

Keywords:
XML queries, XML types, type correctness