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.
Type de document :
Communication dans un congrès
ACM-SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP), Jul 2011, Odense, Denmark. 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00626217
Contributeur : Dario Colazzo <>
Soumis le : vendredi 23 septembre 2011 - 22:56:26
Dernière modification le : jeudi 11 janvier 2018 - 06:23:16

Identifiants

  • HAL Id : inria-00626217, version 1

Collections

Citation

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. 2011. 〈inria-00626217〉

Partager

Métriques

Consultations de la notice

193