Precision and complexity of XQuery type inference

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 (miniXQuery), 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, used in the μXQ+ language, 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.