Deciding Well-Definedness of First-Order, Object-Creating Operations over Tree-Structured

Abstract

The well-definedness problem for a database query language consists of checking, given an expression and an input type, whether the semantics of the expression is defined for all inputs adhering to the input type. In this paper we study the well-definedness problem for a family of first-order, object-creating query languages which are evaluated in a tree-structured, list-based data model. We identify properties of base operations which can make the problem undecidable and give restrictions which are sufficient to ensure decidability. As a direct result, we obtain a large fragment of XQuery for which well-definedness is decidable.