Skip to Main content Skip to Navigation
Conference papers

Precision and Complexity of XQuery Type Inference.

Dario Colazzo 1, 2 Carlo Sartiani 3
2 LEO - Distributed and heterogeneous data and knowledge
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : A key feature of XQuery is its type system. Any language expression is statically typed and its type is used during program type-checking. In XQuery, types of input data and functions are defined in terms of regular expression types, but it is quite easy to write queries that generate non-regular languages. As a consequence, any type system for XQuery has to rely on a type inference process that approximates the (possibly non-regular) output type of a query with a regular type. This approximation process, while mandatory and unavoidable, may significantly decrease the precision of the inferred types. In this paper we will analyze the precision and the complexity of the W3C type inference algorithm. By defining an abstract model for the core of XQuery and for its type language, we will identify the critical issues in the inference process and the sources of precision loss. We will also propose an alternative type inference system, and show that in most cases it is more precise without any performance penalties. Finally, we will identify relevant classes of input types for which inference precision can be dramatically improved.
Document type :
Conference papers
Complete list of metadatas
Contributor : Dario Colazzo <>
Submitted on : Friday, September 23, 2011 - 10:56:26 PM
Last modification on : Tuesday, April 21, 2020 - 1:07:59 AM


  • HAL Id : inria-00626217, version 1



Dario Colazzo, Carlo Sartiani. Precision and Complexity of XQuery Type Inference.. ACM-SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP), Jul 2011, Odense, Denmark. ⟨inria-00626217⟩



Record views