XQuery 1.0 Formal Semantics

W3C Working Draft 07 June 2001

This version:

http://www.w3.org/TR/2001/WD-query-semantics-20010607

Latest version:

http://www.w3.org/TR/query-semantics/

Previous versions:

http://www.w3.org/TR/2001/WD-query-algebra-20010215/
http://www.w3.org/TR/2000/WD-query-algebra-20001204/

Editors:

Peter Fankhauser (GMD-IPSI) <fankhaus@darmstadt.gmd.de>
Mary Fernández (AT&T Labs - Research) <mff@research.att.com>
Ashok Malhotra (Microsoft) <ashokma@microsoft.com>
Michael Rys (Microsoft) <mrys@microsoft.com>
Jérôme Siméon (Bell Labs, Lucent Technologies) <simeon@research.bell-labs.com>
Philip Wadler (Avaya) <wadler@avaya.com>

Copyright ©2001 W3C^® (MIT, INRIA, Keio), All Rights Reserved. W3C liability, trademark, document use and software licensing rules apply.

---

Abstract

This document presents the formal semantics of [XQuery 1.0: A Query Language for XML], an XML query language. This document replaces the [XML Query Algebra].

Status of this document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. The latest status of this document series is maintained at the W3C.

This is a First Public Working Draft for review by W3C Members and other interested parties. This document replaces the [XML Query Algebra]. It is a draft document and may be updated, replaced or made obsolete by other documents at any time. It is inappropriate to use W3C Working Drafts as reference material or to cite them as other than "work in progress". This is work in progress and does not imply endorsement by the W3C membership.

This document has been produced as part of the W3C XML Activity, following the procedures set out for the W3C Process. The document has been written by the XML Query Working Group.

The purpose of this document is to present the current state of the formal semantics of [XQuery 1.0: A Query Language for XML] and to elicit feedback on its current state. The XML Query Working Group feels that it has made good progress on this document but that it is subject to change in future versions. Comments on this document should be sent to the W3C mailing list www-xml-query-comments@w3.org (archived at http://lists.w3.org/Archives/Public/www-xml-query-comments/). Important issues remain open - see [B.3.1 Open Issues]. In particular, the reader should note the following issues related to compatibility of the XQuery formal semantics with related XML activities.

• [Issue-0089:  Syntax for types in XQuery]: The XQuery formal semantics's is based on a subset of the XQuery surface syntax, but some misalignments exist. The XQuery formal semantics presents a syntax for type expressions that is not supported in the XQuery surface syntax. It also has a static type-assertion expression (see [Issue-0090:  Static type-assertion expression]), an attribute constructor expression (see [Issue-0091:  Attribute expression]), and an error expression (see [Issue-0092:  Error expression]) that are not in the XQuery surface syntax

• [Issue-0088:  Align XQuery types with XML Schema : Formal Description.]: The XQuery formal semantics's type system is based on [XML Schema : Formal Description] (XSFD), but some misalignments exist. A related issue is [Issue-0018:  Align algebra types with schema]. We assume that the XQuery formal semantics will be based on XSFD and leave alignment of XSFD and XML Schema for others to resolve.

• [Issue-0056:  Operators on Simple Types]: A joint XSLT/Schema/Query task force is chartered to define the operators on Schema simple types. XQuery will adopt the operators defined by that group.

A list of current W3C Recommendations and other technical documents can be found at http://www.w3.org/TR/.

Table of contents

Appendices

1 Introduction

This document defines the formal semantics of XQuery, an XML query language. The formal semantics of XQuery is defined with respect to a ``core syntax'' of XQuery. XQuery's core syntax is based on a subset of the complete syntax that is available to users, and every expression in the user-level syntax can be rewritten as an expression in the core syntax. Although the intent is for the core syntax to be a proper subset of the complete XQuery syntax, some misalignments exist. The XQuery formal semantics presents a syntax for type expressions that is not supported in the XQuery surface syntax. It also has a static type-assertion expression (see [Issue-0090:  Static type-assertion expression]), an attribute constructor expression (see [Issue-0091:  Attribute expression]), and an error expression (see [Issue-0092:  Error expression]) that are not in the XQuery surface syntax

A forthcoming document defines operators and a library of built-in functions for XQuery and XPath 2.0. In this document, functions in this library have the namespace prefix xfo.

In this document, ``query-analysis time'' refers to when an XQuery expression is parsed and type checked, that is before the value of the expression is computed, and ``query-evaluation time'' refers to when an XQuery expression is evaluated, that is, when it is reduced to a value. We sometimes use the phrases query-analysis time and ``compile time'' interchangeably as well as the phrases query-evaluation time and ``run time''.

This work builds on long-standing traditions in the database community. In particular, we have been inspired by systems such as SQL, OQL, and nested relational algebra (NRA). We have also been inspired by systems such as Quilt, UnQL, XDuce, XML-QL, XPath, XQL, XSLT, and YaTL. We give citations for all these systems below.

In the database world, it is common to translate a query language into an algebra; this happens in SQL, OQL, and NRA, among others. The purpose of the algebra is twofold. First, an algebra is used to give a semantics for the query language, so the operations of an algebra should be well-defined. Second, an algebra is used to support query optimization, so it should possess a rich set of laws. The core syntax of XQuery serves as an algebra for XQuery. The laws we give include analogues of most of the laws of relational algebra.

It is also common for a query language to exploit schemas or types; this happens in SQL, OQL, and NRA, among others. The purpose of types is twofold. Types can be used to detect certain kinds of errors at query-analysis time and to support query optimization. Given the type of input values, a query applied to those values, and the expected type of the query's output value, the XQuery type system can detect at query-analysis time if the query's output value has the expected output type.

DTDs and XML Schema can be thought of as providing something like types for XML. The XQuery formal semantics uses a a type system based on the formalism in [XML Schema : Formal Description]. On this basis, XQuery is statically typed. This allows an implementation of XQuery to determine and check at query-analysis time the output type of a query on documents conforming to an input type. Compare this to an untyped or dynamically typed query language, where each individual output has to be validated against a schema at query-evaluation time, and there is no guarantee that this check will always succeed.

To define the XQuery completely, we present a static semantics and a dynamic semantics. The static semantics is presented as type inference rules, which relate XQuery expressions to types and and specify under what conditions an expression is well typed. The semantics is static, because ill-typed expressions are identified at query-analysis time, i.e., before the query is evaluated. The dynamic, or operational, semantics is presented as value inference rules, which relate XQuery expressions to values. XQuery's values are defined in the [XQuery 1.0 and XPath 2.0 Data Model]; for example, they include XML simple values, attributes, and elements, as well as other values. A dynamic semantics guarantees that every expression can be reduced to a value and may serve as the basis for a query interpreter or compiler.

The document is organized as follows. A tutorial introduction is presented in [2 XQuery Semantics by Example]. The primary purpose of this tutorial to present various features of XQuery and to show how a type is computed for each XQuery expression. The reader is referred to [XQuery 1.0: A Query Language for XML] for a complete tutorial on XQuery's features. The grammar of XQuery's core syntax and the grammar for types are given in [3 XQuery Core Syntax]. We give the static typing rules for XQuery in [4 Static Semantics : Type-Inference Rules] and then the dynamic semantics for XQuery in [5 Dynamic Semantics : Value-Inference Rules]. These sections formalize the information presented informally in [2 XQuery Semantics by Example]. Although these two sections contain the most challenging material, we have tried to make the content as accessible as possible. Readers only interested in learning about XQuery's features need not read these sections, however, we expect that implementors of XQuery will read them. Finally, in [6 XQuery Mapping to Core], we present the mapping from complete syntax of XQuery to the core syntax. We note here that this section is still preliminary and contains inconsistencies (see [Issue-0099:  Incomplete/inconsistent mapping from XQuery to core ]).

In [B.2 Issues list], we discuss open issues and problems. We present some equivalence and optimization laws of XQuery in [A Equivalences].

Cited literature includes: monads [Mog89], [Mog91], [Wad92], [Wad93], [Wad95], NRA [BNTW95], [Col90], [LW97], [LMW96], OQL [BK93], [BKD90], [CM93], Quilt [Quilt], SQL [Date97], UnQL [BFS00], XDuce [HP2000], XMSL-QL [XMLQL99], XPath [XPath], XQL [XQL99], XSLT [XSLT 99], and YaTL [YAT99].

2 XQuery Semantics by Example

For a complete introduction to XQuery, see [XQuery 1.0: A Query Language for XML]. This document focuses on the static type and dynamic operational semantics of XQuery. This section introduces the static and dynamic semantics of XQuery, using examples based on accessing a database of books.

2.1 Data and types

Consider the following sample data:

    <bib>
      <book year="1999" isbn="1-55860-622-X">
        <title>Data on the Web</title>
        <author>Abiteboul</author>
        <author>Buneman</author>
        <author>Suciu</author>
      </book>
      <book year="2001" isbn="1-XXXXX-YYY-Z">
        <title>XML Query</title>
        <author>Fernandez</author>
        <author>Suciu</author>
      </book>
    </bib>

Here is a fragment of an XML Schema for such data:

    <xs:group name="Bib">
      <xs:element name="bib">
        <xs:complexType>
          <xs:group ref="Book"
                     minOccurs="0" maxOccurs="unbounded"/>
        </xs:complexType>
      </xs:element>
    </xs:group>
    
    <xs:group name="Book">
      <xs:element name="book">
        <xs:complexType>
          <xs:attribute name="year" type="xs:integer"/>
          <xs:attribute name="isbn" type="xs:string"/>
          <xs:element name="title" type="xs:string"/>
          <xs:element name="author"type="xs:string" maxOccurs="unbounded"/>
        </xs:complexType>
      </xs:element>
    </xs:group>

In the XQuery formal semantics, we present a syntax for type expressions that allows us to explain how the type of an XQuery expression is inferred. This type syntax is not in the XQuery surface syntax (see [Issue-0089:  Syntax for types in XQuery]. In addition, the XQuery formal semantics includes an expression that asserts statically the type of an expression (see [Issue-0090:  Static type-assertion expression]), an attribute constructor expression (see [Issue-0091:  Attribute expression]), and an error expression (see [Issue-0092:  Error expression]) that are not in the XQuery surface syntax. With the exception of type expressions and the static type-assertion expression, all other XQuery expressions in this document are in the XQuery surface syntax. The data and schema above is represented as follows:

    TYPE Bib = ELEMENT bib (Book*)
    TYPE Book =
      ELEMENT book
        ( ATTRIBUTE year  (xs:integer) &
          ATTRIBUTE isbn  (xs:string)
          ELEMENT   title (xs:string), 
          (ELEMENT   author(xs:string))+
        )
    LET $bib0 := 
    <bib>
      <book year="1999" isbn="1-55860-622-X">
        <title>Data on the Web</title>
        <author>Abiteboul</author>
        <author>Buneman</author>
        <author>Suciu</author>
      </book>
      <book year="2001" isbn="1-XXXXX-YYY-Z">
        <title>XML Query</title>
        <author>Fernandez</author>
        <author>Suciu</author>
      </book>), 
    </bib> : Bib 
    RETURN ...

The expression above defines two types, Bib and Book, and defines one variable, $bib0.

The Bib type corresponds to a single bib element, which contains a sequence of zero or more Book elements. Every attribute or element can be viewed as a sequence of length one.

The Book type corresponds to a single book element, which also contains a sequence of zero or more attributes and elements. It contains one year attribute and one isbn attribute, followed by one title element, followed by one or more author elements. The & operator, called the interleave operator, indicates that the year and isbn attributes may occur in any order. A isbn attribute and a title or author element contains a string value, and a year attribute contains an integer.

The let expression above binds the variable $bib0 to a literal XML value. The variable $bib0 is in scope for all expressions in the body of the RETURN clause. For convenience, the RETURN ... indicates that the expressions in the rest of this document are contained within the scope of this LET expression. The value of a variable is immutable, that is, once a variable is defined, its value does not change. The value of $bib0 is a bib element that contains two book elements.

XQuery is a strongly typed language, therefore the value of $bib0 must be an instance of its declared type, or the expression is ill-typed. Here the value of $bib0 is an instance of the Bib type, because it contains one bib element, which contains two book elements, each of which contain an integer-valued year attribute, a string-valued isbn attribute, a string-valued title element, and one or more string-valued author elements.

For convenience, we define a second global variable $book0 also bound to a literal value, which is equal to the first book in bib0.

    LET $book0 :=
      <book year="1999" isbn="1-55860-622-X">
        <title>Data on the Web</title>
        <author>Abiteboul</author>
        <author>Buneman</author>
        <author>Suciu</author>
      </book> : Book
    RETURN ...

2.2 Projection

One of XQuery's most basic operations is projection. The following expression returns all author elements contained in book elements contained in $bib0:

    $bib0/book/author
==>(<author>Abiteboul</author>,
    <author>Buneman</author>,
    <author>Suciu</author>,
    <author>Fernandez</author>,
    <author>Suciu</author>)
:   (ELEMENT author (xs:string))*
 

Note that in the result, the document order of author elements is preserved.

The above example and the ones that follow have three parts. First is an expression in XQuery. Second, following the ==> is the value of this expression. Third, following the : is the type of the expression, which is (of course) also a legal type for the value.

It may be unclear why the type of $bib0/book/author contains zero or more authors, even though the type of a book element contains one or more authors. Let's look at the derivation of the result type by looking at the type of each sub-expression:

    $bib0             : Bib
    $bib0/book        : Book*
    $bib0/book/author : (ELEMENT author (xs:string))*
 

Recall that Bib, the type of bib0, may contain zero or more Book elements, therefore the expression bib0/book might contain zero book elements, in which case, bib0/book/author would contain no authors.

This illustrates an important feature of the type system: the type of an expression depends only on the type of its sub-expressions. It also illustrates the difference between an expression's value at query-evaluation time and its type at query-analysis time. Since the type of $bib0 is Bib, the best type for $bib0/book/author is one listing zero or more authors, even though for the given value of $bib0, the expression will always contain exactly five authors.

Its also possible to project on attributes. This expression produces the year attribute of $book0 whose type is ATTRIBUTE year (xs:string).

    $book0/@year
==> ATTRIBUTE year "1999"
:   ATTRIBUTE year (xs:string)
 

2.3 Simple data

One may access simple data (strings, integers, or booleans) using the keyword data(). For instance, if we wish to select all author names in a book, rather than all author elements, we could write the following.

    $book0/author/data()
==> ("Abiteboul",
     "Buneman",
     "Suciu")
:   xs:string+

Similarly, it is possible to project the simple values of attributes. The following returns the year the book was published.

    $book0/@year/data()
==> 1999
:   xs:integer

The data() operator has a similar purpose to the the text() node test in XPath 1.0, in that they both project the atomic values in a document. In XPath 1.0, text selects the text node children of an element node, where as in XQuery, data returns the simple-typed value of the element node. We chose the keyword data() because, as the second example shows, not all data items are strings.

2.4 Iteration

Another common operation is to iterate over elements in a document so that their content can be transformed into new content. Here is an example of how to process each book to list the author before the title, and remove the year and isbn.

    FOR $b IN $bib0/book RETURN
      <book> { $b/author, $b/title } </book>
==> (<book>
       <author>Abiteboul</author>
       <author>Buneman</author>
       <author>Suciu</author>
       <title>Data on the Web</author>
     </book>, 
     <book> 
       <author>Fernandez</author>
       <author>Suciu</author>
       <title>XML Query</author>
     </book>)
:   (ELEMENT book(
      (ELEMENT author(xs:string))+,
      ELEMENT title(xs:string))
    )* 

The for expression iterates over all book elements in $bib0, and binds the variable $b to each such element. For each element bound to $b, the inner expression constructs a new book element containing the book's authors followed by its title. The transformed elements appear in the same order as they occur in $bib0.

In the result type, a book element is guaranteed to contain one or more authors followed by one title. Let's look at the derivation of the result type to see why:

    $bib0/book        : Book*
    $b                : Book
    $b/author         : (ELEMENT author(xs:string))+
    $b/title          : ELEMENT title (xs:string)

The type system can determine that $b is always Book, therefore the type of $b/author is (ELEMENT author(xs:string))+, and the type of $b/title is ELEMENT title (xs:string).

In general, the value of a for expression is a sequence of zero or more data-model values as defined in [XQuery 1.0 and XPath 2.0 Data Model]. If the body of the for expression itself yields a sequence, then all of the sequences are concatenated together. For instance, the expression:

    FOR $b IN $bib0/book RETURN
      $b/author

is exactly equivalent to the expression $bib0/book/author.

2.5 Selection

To select values that satisfy some predicate, we use the where expression. For example, the following expression selects all book elements in $bib0 that were published before 2000.

    FOR $b IN $bib0/book 
    WHERE $b/@year/data() <= 2000 RETURN
      $b
==> <book year="1999" isbn="1-55860-622-X">
     <title>Data on the Web</title>
     <author>Abiteboul</author>
     <author>Buneman</author>
     <author>Suciu</author>
    </book>
:   Book* 

In general, an expression of the form:

where e₁ return e₂

is converted to the form

if e₁ then e₂ else ()

WHERE e₁ and e₂ are expressions. Here () is an expression that stands for the empty sequence, a sequence that contains no attributes or elements. We also write () for the type of the empty sequence.

According to this rule, the expression above translates to

FOR $b IN $bib0/book RETURN
  IF $b/@year/data() <= 2000 THEN $b ELSE () 

and this has the same value and the same type as the preceding expression.

2.6 Quantification

The following expression selects all book elements in $bib0 that have some author named "Buneman".

    FOR $b IN $bib0/book 
    WHERE SOME $a IN $b/author SATISFIES $a/data() = "Buneman" RETURN
      $b
==> <book year="1999" isbn="1-55860-622-X">
     <title>Data on the Web</title>
     <author>Abiteboul</author>
     <author>Buneman</author>
     <author>Suciu</author>
    </book>
:   Book*

We can use the every expression to find all books where all the authors are Buneman:

    FOR $b IN $bib0/book 
    WHERE EVERY $a IN $b/author SATISFIES $a/data() = "Buneman" RETURN
      $b
==> ()
:   Book*

There are no such books, so the result is the empty sequence.

2.7 Join

Another common operation is to join values from one or more documents. To illustrate joins, we give a second data source that defines book reviews:

    TYPE Reviews  =
      ELEMENT reviews (
        (ELEMENT book (
          ELEMENT title  (xs:string),
          ELEMENT review (xs:string))
        )*
      )
    LET $review0 :=
      <reviews>
        <book>
          <title>XML Query</title>
          <review>A darn fine book.</review>
        </book>,
        <book>
          <title>Data on the Web</title>
          <review>This is great!</review>
        </book>
      </review> : Reviews
    RETURN ...

The Reviews type contains one reviews element, which contains zero or more book elements; each book contains a title and a review.

We can use nested for expressions to join the two sources $review0 and $bib0 on title values. The result combines the title, authors, and reviews for each book.

    FOR $b IN $bib0/book, $r IN $review0/book 
    WHERE $b/title/data() = $r/title/data() RETURN
      <book>{ $b/title, $b/author, $r/review }</book>
==> (<book>
       <title>Data on the Web</title>
       <author>Abiteboul</author>
       <author>Buneman</author>
       <author>Suciu</author>
       <review>A darn fine book.</review>
     </book>,
     <book>
       <title>XML Query</title>
       <author>Fernandez</author> 
       <author>Suciu</author>
       <review>This is great!</review>
     </book>)
:   (ELEMENT book(
      ELEMENT title  (xs:string),
      (ELEMENT author (xs:string))+,
      ELEMENT review (xs:string))
    )*

Note that the outer-most for expression determines the order of the result. Readers familiar with optimization of relational join queries know that relational joins commute, i.e., they can be evaluated in any order. This is not true for XQuery: changing the order of the first two for expressions would produce different output. In [2.8 Unordered built-in function], we introduce support for unordered sequences, which permits commutable joins.

It is beyond the scope of this document to describe algorithms for evaluating nested loop joins. See [Graefe93] for a survey.

2.8 Unordered built-in function

As discussed in [2.7 Join] joins do not commute on ordered forests. In databases, ordering often does not matter. To permit commutable joins, and to allow for other query optimization techniques, XQuery also allows to explicitly disregard the order of a sequence. This is accomplished by the built-in function UNORDERED. The expression UNORDERED(Expr) may return any permutation of the sequence returned by Expr. For example, when applying UNORDERED to the join-query [2.7 Join], the result may be either ordered as in [2.7 Join] or as below:

    UNORDERED(
      FOR $b IN $bib0/book, $r IN $review0/book 
      WHERE $b/title/data() = $r/title/data() RETURN
        <book> { $b/title, $b/author, $r/review } </book>
    )
==> (<book>
       <title>XML Query</title>
       <author>Fernandez</author>
       <author>Suciu</author>
       <review>This is great!</review>
     </book>,
     <book>
       <title>Data on the Web</title>
       <author>Abiteboul</author>
       <author>Buneman</author>
       <author>Suciu</author>
       <review>A darn fine book.</review>
     </book>)
:   ELEMENT book (
      ELEMENT title  (xs:string),
      ELEMENT author (xs:string)+,
      ELEMENT review (xs:string)
    )*

The expression UNORDERED(Expr) satisfies some useful laws that can be used for optimization. E.g., UNORDERED distributes over FOR, and nested FOR expressions on UNORDERED expressions are commutative; see also Rules 12--18 in [A.2 Laws]. On this basis joins can be commuted, i.e., switching the inner FOR expression with the outer FOR expression, does not change the semantics of the above query:

    UNORDERED(
      FOR $r IN $review0/book, $b IN $bib0/book 
      WHERE $b/title/data() = $r/title/data() RETURN
        <book> { $b/title, $b/author, $r/review } </book>
    )

Note that unordered sequences are currently not distinguished from ordered sequences at type level. This is mainly for two reasons: (1) XML Schema does not distinguish between unordered sequences and ordered sequences and (2) the distinction requires to overload all built-in operators for sequences, such as FOR, DISTINCT, as well as user defined functions on sequences.

2.9 Parent and treat operators

Many of the previous queries select values and return them or use them in the construction of new values. Once a value is selected, however, the previous queries do not access the original source of the selected value, i.e., the document or hierarchy of elements in which the selected value is contained. It is sometimes useful, however, to access or preserve the original context of selected nodes.

Consider the following example, which contains a new bibliography of articles in bib1:

    TYPE Bib1 = <bib>Article*</bib>
    TYPE Article =
      ELEMENT article(
        ATTRIBUTE year (xs:integer),
        ELEMENT title  (xs:string),
        ELEMENT journal(xs:string),
        (ELEMENT author (xs:string))+
      )
    LET $bib1 :=
      <bib>
        <article year="2000">
          <title>Queries and computation on the web</title>
          <journal>Theoretical Computer Science</journal>
          <author>Abiteboul</author>
          <author>Vianu</author>
        </article>
      </bib> : Bib1
    RETURN ...

Assume there exists a full-text search function, contains, which given a set of documents, selects elements that contain a particular keyword. (This function is not defined in XQuery, but is used here to illustrate a point.) The details of function application and declaration are given in [2.18 Functions].

The following expression returns those elements in bib0 and bib1 that contain the keyword "Abiteboul". Note that the result type of the expression is AnyTree*. This is because the contains function cannot know apriori which elements, if any, contain a given keyword.

    FOR $a IN contains(($bib0, $bib1), "Abiteboul") RETURN
      $a
==> (<author>Abiteboul<author>, <author>Abiteboul</author>)
:   AnyTree*

The result above does not provide the context in which the two author elements occur. Even if the contains function did return more context, it might be useful to browse the context in which they occurred, for example, by accessing their parent and/or sibling elements. The built-in function parent accesses the parent of an attribute or element. For example, this expression returns more useful information than the previous one:

    FOR $a IN contains(($bib0, $bib1),  "Abiteboul") RETURN
      $a/..
==> (<book year="1999" isbn="1-55860-622-X">
       <title>Data on the Web</title>
       <author>Abiteboul</author>
       <author>Buneman</author>
       <author>Suciu</author>
     </book>, 
     <article year="2000">
       <title>Queries and computation on the web</title>
       <journal>Theoretical Computer Science</journal>
       <author>Abiteboul</author>
       <author>Vianu</author>
     </article>)
:   AnyElement*

Note that the result type of the expression is AnyElement*. When applied to an attribute or element value, the parent function always has return type AnyElement?, i.e., zero or one AnyElement. This is because XQuery's type system only preserves type information about an attribute or element's content, not about its containing parent.

It is possible to recover more precise type information with the dynamic or run-time treat operator, which attempts to cast at run time an expression to a given type. If the expression does not have the given type, a run-time error is raised. Dynamic casts are necessary when it not possible to determine at query-analysis time the most precise type of a value; they are sometimes called ``down casts''.

For example, the use of parent in the following expression loses some useful type information, that is that p is a Book. We can recover more precise information by casting p to the Book type:

    FOR $p IN $book0/title/.. RETURN
      TREAT AS Book ($p)
==> <book year="1999" isbn="1-55860-622-X">
      <title>Data on the Web</title>
      <author>Abiteboul</author>
      <author>Buneman</author>
      <author>Suciu</author>
    </book>
:   Book?

The result type is Book? because the parent function has type AnyElement?. If we try erroneously to cast p to an Article, the error value is returned. Its type is again Article?, because AnyElement could be an Article:

    FOR $p IN $book0/title/.. RETURN
      TREAT AS Article ($p)
==> error
:   Article?

However, if we try to cast $book0 to an Article, the result type becomes Ø, the empty choice, because we can statically determine that a Book is not an Article.

    FOR $p IN $book0 RETURN
      TREAT AS Article ($p)
==> error
:   0

We have already seen many examples of static or compile-time casting. A static cast permits the type of an expression to be changed and checked at query-analysis time; they are sometimes called ``up casts''. For example, consider the type Book0, which permits a book to have zero or more authors.

    TYPE Book0 =
      ELEMENT book(
        ATTRIBUTE year (xs:integer) &
        ATTRIBUTE isbn (xs:string),
        ELEMENT title  (xs:string),
        (ELEMENT author (xs:string))*
      )

The explicit-type expression e : t statically casts a value to the given type. For example, the expression below statically casts $book0 to Book0; this is permissible because the type of $book0 at query-analysis time is a sub-type of Book0.

    $book0 : Book0
==> <book year"1999" isbn="1-55860-622-X">
      <title>Data on the Web</title>
      <author>Abiteboul</author>
      <author>Buneman</author>
      <author>Suciu</author>
    </book>
:   Book0

If we try erroneously to cast $book0 to a more precise type (e.g., a book with 4 or more authors), a type error will occur at query-analysis time.

2.10 References and node identity

The uses of the parent operator in [2.9 Parent and treat operators] show that it is possible to access the original context of nodes. This is possible because the XML Query Data Model supports node identity, that is, every instance of a node (e.g., element, attribute, processing instruction, and comment) in the data model has a unique identity. We can compare the identity of two nodes for equality using the == operator. For example, in the following expression, two distinct element nodes are created and bound to variables a1 and a2. Although the two nodes are structurally equal, their identities are not equal:

   
    LET $a1 := <author>Suciu</author>, 
        $a2 := <author>Suciu</author> 
    RETURN 
      $a1 == $a2
==> false
:   xs:boolean

In general, all XQuery's operators preserve node identity. There is one exception: the element constructor, which given a tag name and a sequence of children nodes, constructs a new element. A new element's content does not refer directly to the given children nodes, but to copies of these nodes. For example, the following expression constructs an element with name newbook and content $book0/author, $book0/title:

    LET $book1 := 
      <newbook> 
          { $book0/author, $book0/title } 
      </newbook>
    RETURN $book1
==> <newbook>
      <author>Abiteboul</author>
      <author>Buneman</author>
      <author>Suciu</author>
      <title>Data on the Web</title>
    </newbook>
:   ELEMENT newbook (
      (ELEMENT author (xs:string))+,
      ELEMENT title  (xs:string)
    ) 

The newbook element contains copies of the nodes in the sequence $book0/author, $book0/title, not the original nodes in $book0. Copying guarantees that a node is always the parent of its child nodes and a node is always the child of its parent; these constraints are invariants of [XQuery 1.0 and XPath 2.0 Data Model]. For example, we would expect that the following expression is always true:

    $book1/author/.. == $book1 

    $book1/author/.. == $book0 

Sometimes it is useful to construct elements that do preserve the identity of its child nodes, for example, when constructing a view of one or more XML documents. In this case, we want the new element to contain references to, not copies of, the original nodes. The ref operator constructs a reference to a node. For example, book2 below contains references to the nodes in $book0:

    LET $book2 := 
      <newbook> 
        { (FOR $a IN $book0/author RETURN ref($a)), 
          ref($book0/title)
        } 
      </newbook>
    RETURN $book2
==> <newbook>
      <q:ref><author>Abiteboul</author></q:ref>
      <q:ref><author>Buneman</author></q:ref>
      <q:ref><author>Suciu</author></q:ref>
      <q:ref><title>Data on the Web</title></q:ref>
    </newbook>
:   ELEMENT newbook (
      (REFERENCE (ELEMENT author (xs:string)))+, 
      REFERENCE (ELEMENT title  (xs:string))
    ) 

Ed. Note: MF : Issue - serialized representation of Data Model reference nodes.

Note that the type of the expression contains reference types. The deref operator dereferences a reference value. In the following, it returns the elements in $book0.

    FOR $v IN $book2/* RETURN deref($v)
==> (<author>Abiteboul</author>, 
     <author>Buneman</author>,
     <author>Suciu</author>,
     <title>Data on the Web</title>)
:   (ELEMENT author (xs:string))+,
    ELEMENT title  (xs:string) 

For convenience, the expression above can be also be written as $book2/deref().

2.11 Restructuring and grouping

Often it is useful to regroup elements in an XML document. For example, each book element in $bib0 groups one title with multiple authors. This expression groups each author with the titles of his/her publications.

    FOR $a IN distinct-value($bib0/book/author/data()) RETURN
      <biblio>
        <author>{ $a }</author>
        { FOR $b IN $bib0/book, $a2 IN $b/author/data()
          WHERE $a = $a2 RETURN
            $b/title
        }
      </biblio>
==> (<biblio> 
       <author>Abiteboul</author>
       <title>Data on the Web</title>
     </biblio>,
     <biblio> 
       <author>Buneman</author> 
       <title>Data on the Web</title>
     </biblio>,
     <biblio> 
       <author>Suciu</author> 
       <title>Data on the Web</title> 
       <title>XML Query</title>
     </biblio>,
     <biblio> 
       <author>Fernandez</author> 
       <title>XML Query</title>
     </biblio>)
:   (ELEMENT biblio (
      ELEMENT author (xs:string),
      (ELEMENT title  (xs:string))*)
    )*

Readers may recognize this expression as a self-join of books on authors. The expression distinct-value($bib0/book/author/data()) produces a sequence of author names whose values are all distinct. The outer for expression binds $a to the name of each author element, and the inner for expression selects the title of each book that has some author whose name equals $a.

Here distinct-value is an example of a built-in function. It produces a sequence of nodes whose values are all distinct, i.e., there are no duplicate values; the order of the resulting sequence is not defined. The builtin function distinct-node produces a sequenc of nodes whose identities are all distinct.

The type of the result expression may seem surprising: each biblio element may contain zero or more title elements, even though in $bib0 every author co-occurs with a title. Recognizing such a constraint is outside the scope of the type system, so the resulting type is not as precise as we would like.

2.12 Querying order

Ed. Note: MF: Clearly, the following example of index is not appropriate for a tutorial -- it is only used to define RANGE.

Often it is useful to query the order of elements in an sequence or a document. There are two kinds of order among elements: local order and document (or global) order. XQuery supports querying of local and global order.

Local order refers to the order among sibling elements in an sequence. To query local order, the index function pairs an integer index with each element in an sequence:

    index($book0/author)
==> (<q:pair><q:fst>1</q:fst>
            <q:snd><q:ref><author>Abiteboul</author></q:ref></q:snd></q:pair>,
     <q:pair><q:fst>2</q:fst>
            <q:snd><q:ref><author>Buneman</author></q:ref></q:snd></q:pair>
     <q:pair><q:fst>3</q:fst>
            <q:snd><q:ref><author>Suciu</author></q:ref></q:snd></q:pair>)
:   (ELEMENT q:pair(
      ELEMENT q:fst (xs:integer),
      ELEMENT q:snd (REFERENCE (ELEMENT author (xs:string))))
    )+

The index function uses reference in order to preserve node identity when accessing local order. Note that the result type takes into account that at least one pair exists in the result, as $book0/author always contains one or more authors.

Once we have paired authors with an integer index, we can select the first two authors:

    FOR $p IN index($book0/author)
    WHERE ($p/q:fst/data() <= 2) RETURN
      $p/q:snd/deref()
==> (<author>Abiteboul</author>,
     <author>Buneman</author>)
:   (ELEMENT author (xs:string))*

The for expression iterates over all pair elements produced by the index expression. It selects elements whose index value in the q:fst element is between one and two inclusive, and it returns the original content by dereferencing the content of the q:snd element.

The result type may be surprising, because the Book type guarantees that each book has at least one author. However, the type system cannot determine that the conditional where expression will always succeed, so the inner expression may produce zero results. (A sophisticated analysis might improve type precision, but is likely to require much work for little benefit.)

Document (or global) order refers to the total order among all elements in a document. Global order is defined as the order of appearance of the element nodes when performing a pre-order, depth-first traveral of a tree. This corresponds to the order of appearance of their opening tags in the XML serialization. This is equivalent to the definition used in [XPath].

To query global order, the xfo:node-before function can be applied to two nodes. It returns true if the first node is before (and different from) the second node in document order. It returns false if the first node is equal to or after the second node in document order. It raises an error if the nodes are in different documents. For example, the nodes bib0 and review0 are unrelated therefore comparing their order raises an error:

    xfo:node-before($bib0, $review0)
==> ERROR
:   0

The xfo:node-after function is defined similiarly.

Using global order, the following expression returns all author nodes appearing after a book written in 2001:

    FOR $b IN $bib0/book
    WHERE $b/@year/data() = 2001 RETURN
      (FOR $a IN $bib0/book/author 
       WHERE $b before $a RETURN $a)
==> (<author>Fernandez</author>, 
     <author>Suciu</author>)
:   (ELEMENT author (xs:string))*

Note that the root element of a document is before any other element. More generally, an element is before all of its children. For example, the set of elements that are before $bib0 is empty:

    
    empty(FOR $b IN $bib0/book
          WHERE $b before $bib0 $b RETURN 
            $b)
==> true
:   xs:boolean

XQuery supports global order only for elements within the same document. Support for global order among elements in distinct documents is discussed in [Issue-0003:  Global Order].

2.13 Sorting

To sort a sequence, XQuery provides a sort expression, whose form is: Expr₁ sortby Expr₂. The built-in variable '.', called dot, ranges over the items in the sequence Expr₁ and sorts those items using the key value defined by Expr₂. For example, this expression sorts book elements in $review0 by their titles.

    $review0/book SORTBY ./title/data()
==> (<book>
       <title>Data on the Web</title>
       <review>This is great!</review>
     </book>,
     <book>
       <title>XML Query</title>
       <review>This is pretty good too!</review>
     </book>)
:   (ELEMENT book (
      ELEMENT title (xs:string), 
      ELEMENT review (xs:string))
    )*

The sort expression is a restricted form of higher-order function, i.e., it takes a function as an argument. In this case, sort takes a single function, which extracts the key value from each element. The sort expression requires that the less-than inequality, <, be defined for the type of Expr₂.

2.14 Aggregation

We have already seen two built-in functions: index and distinct-value. In addition to these functions, XQuery has five built-in aggregation functions: avg, count, max, min, and sum.

This expression selects books that have more than two authors:

    FOR $b IN $bib0/book
    WHERE count($b/author) > 2 RETURN
      $b
==> <book year="1999" isbn="1-55860-622-X">
      <title>Data on the Web</title>
      <author>Abiteboul</author>
      <author>Buneman</author>
      <author>Suciu</author>
    </book>
:   Book*

All the aggregation functions take a sequence with repetition type and return an integer value; count returns the number of elements in the sequence.

2.15 Expanded names

So far, all our examples of attributes and elements use unqualified local names, i.e., names that do not include an explicit namespace URI. It is also possible to specify and match on the expanded name of an attribute or element. The expanded name Namespace:LocalName consists of a namespace URI Namespace and a local name LocalName.

Consider an inventory of books that contains data from both http://www.BooksRUs.com and http://www.cheapBooks.com. In this example, the first element contains values whose names are defined in the BooksRUs.com namespace, and the second element contains values whose names are defined in the cheapBooks.com namespace:

    NAMESPACE booksRus = "http://www.BooksRUs.com/books.xsd"
    NAMESPACE cheapBooks = "http://www.cheapBooks.com/ourschema.xsd"
    TYPE Inventory = <inv> InvBook* </inv>
    LET $inventory := 
      <inv>
        <booksRus:book year="1999" isbn="1-55860-622-X">
          <booksRus:title>Data on the Web</booksRus:title>
          <booksRus:author>Abiteboul</booksRus:author>
          <booksRus:author>Buneman</booksRus:author>
          <booksRus:author>Suciu</booksRus:author>
        </booksRus:book>
        <cheapBooks:book year="2001">
          <cheapBooks:title>XML Query</cheapBooks:title>
          <cheapBooks:author>Fernandez</cheapBooks:author>
          <cheapBooks:author>Suciu</cheapBooks:author>
          <cheapBooks:isbn>1-XXXXX-YYY-Z</cheapBooks:isbn>
        </cheapBooks:book>
      </inv> : Inventory
    RETURN ...

In this example, elements imported from existing schemas each refer to a single namespace, thus the definition of InvBook is:

    TYPE BooksRUBook = 
      ELEMENT booksRus:book (
        ATTRIBUTE year (xs:integer) &
        ATTRIBUTE isbn (xs:string),
        ELEMENT booksRus:title(xs:string)
        (ELEMENT booksRus:author(xs:string))+
      )
    TYPE CheapBooksBook = 
      ELEMENT cheapBooks:book (
        ATTRIBUTE year (xs:integer), 
        ELEMENT cheapBooks:title (xs:string), 
        (ELEMENT cheapBooks:author(xs:string))+
        ELEMENT cheapBooks:isbn  (xs:string)
      )
    TYPE InvBook = BooksRUBook | CheapBooksBook

Here vertical bar (|) is used to indicate a choice between types: each InvBook is either a BooksRUBook or a CheapBooksBook.

We have already seen how to project on the constant name of an attribute or element. It is also useful to project on wildcards, which are used to match names with any namespace and/or any local name. For example, this expression matches elements with any local name and with namespace URI http://www.BooksRUs.com/books.xsd:

    $inventory/booksRus:* 
==> <booksRus:book year="1999" isbn="1-55860-622-X">
      <booksRus:title>Data on the Web</booksRus:title>
      <booksRus:author>Abiteboul</booksRus:author>
      <booksRus:author>Buneman</booksRus:author>
      <booksRus:author>Suciu</booksRus:author>
    </booksRus:book>
: ELEMENT booksRus:book (
    ATTRIBUTE year (xs:integer) &
    ATTRIBUTE isbn (xs:string),
    ELEMENT booksRus:title  (xs:string)
    (ELEMENT booksRus:author (xs:string))+
  )

Similarly, this expression first projects elements in any namespace whose local name is book and then projects on their year attributes:

    $inventory/*:book/@year
==> (ATTRIBUTE year (1999), ATTRIBUTE year (2001))
:   (ATTRIBUTE year (xs:integer))*

Ed. Note: MF: Open issue whether *:localname will be supported.

The expression Expr/a is shorthand for Expr/ns:a, where ns is the default namespace. Similarly, * is shorthand for ns:*, i.e., any name in the default namespace.

2.16 Comments and processing instructions

In an XML document, comments and processing instructions may appear anywhere outside other markup[XML]. Processing instructions permit documents to contain instructions for applications. Comments and processing instructions are not part of the document's character data. An XML processor may, but need not, make the text of comments available to an application, but it must pass processing instructions to the application. The processing instruction begins with a target used to identify the application to which the instruction is directed.

XQuery supports comments and processing instructions in types and expressions. The type expression PIC(t) denotes a value in which zero or more processing instructions and comments may be interleaved arbitrarily with the nodes in type t. For example, the two element types BibPIC and BookPIC permit PIs and comments to be interleaved with their content:

    TYPE BibPIC  = ELEMENT bib (pic(BookPIC*))
    TYPE BookPIC = 
      ELEMENT book (
        ATTRIBUTE year (xs:integer) &
        ATTRIBUTE isbn (xs:string),
        PIC (ELEMENT title (xs:string), (ELEMENT author(xs:string))+)
      )

We can construct processing instruction and comment values using the built-in constructors processing_instruction and comment:

     LET $bibpc0 := 
      <bib>
         { comment("Canonical XQuery  example.") } 
         <book year="1999" isbn="1-55860-622-X">
            { comment("First book example"), 
              processing_instruction("Publisher.asp", 
                "publisher=http://www.mkp.com") }
            <title>Data on the Web</title>
            <author>Abiteboul</author>
            <author>Buneman</author>
            <author>Suciu</author>
         </book>
         <book year="2001" isbn="1-XXXXX-YYY-Z">
            <title>XML Query"</title>
            { comment("Second book example") }
            <author>Fernandez</author>
            <author>Suciu</author>
         </book>
      </bib> : BibPIC
    RETURN ...

Finally, we can project on processing instructions and comments, in the same way we project on children, attributes, and simple content:

    
    $bibpc0/book/comment()
==> (comment("First book example"), comment("Second book example"))
:   Comment*

    $bibpc0/book/processing_instruction()
==> processing_instruction("Publisher.asp", "publisher=http://www.mkp.com")
:   ProcessingInstruction*

Comments and processing instructions may be ignored by an XML processor, in which case they would not even be accessible to a query processor. If they are not ignored, however, comments and processing instructions are typed values and are treated like any other value in an XQuery expression.

2.17 Mixed Content

An element type has mixed content when elements of that type may contain character data, optionally interspersed with child elements[XML]. The type expression mixed(t) denotes a value in which zero or more xs:string values may be interleaved arbitrarily with the nodes in type t. For example, the content of the review element contains a reviewer element, which may be interleaved with string values:

    TYPE ReviewsMixed  =
      ELEMENT reviews (
        (ELEMENT book (
          ELEMENT title (xs:string),
          ELEMENT review (MIXED (ELEMENT reviewer(xs:string)))))*
      )

Here are two examples of mixed content, in which the text of the book review may be interleaved with the name of the reviewer:

    LET $reviewmix0 :=
      <reviews>
        <book>
          <title>XML Query</title>
          <review>A darn fine book: <reviewer>XML On-line</reviewer></review>
        </book>
        <book>
          <title>Data on the Web</title>, 
          <review>The <reviewer>publisher</reviewer> says 'This is great!'</review>
        <book>
      </reviews> : ReviewsMixed
    RETURN ...

It is often useful to concatenate all the string values of a mixed-content element to recover its complete text value. We use the builtin function string_value; as defined in XPath [XPath], the string value of a node is determined by its kind, e.g., element, attribute, etc.

    FOR $b IN $reviewmix0/book RETURN 
      string_value($b/review)
==> ("A darn fine book : XML On-line",
     "The publisher says 'This is great!'")
:   xs:string*

2.18 Functions

Functions can make queries more modular and concise. Recall that we used the following query to find all books that do not have "Buneman" as an author.

    FOR $b IN $bib0/book
    WHERE EVERY $a IN $b/author SATISFIES NOT($a/data() = "Buneman") RETURN
      $b
==> <book year="2001" isbn="1-XXXXX-YYY-Z">
      <title>XML Query</title>
      <author>Fernandez</author>
      <author>Suciu</author>
    </book>
:   Book*

A different way to formulate this query is to first define a function that takes a string s and a book b as arguments, and returns true if book b does not have an author with name s.

    DEFINE FUNCTION notauthor (xs:string $s, Book $b) RETURNS xs:boolean {
      EVERY $a IN $b/author SATISFIES NOT($a/data() = $s)
    }

The query can then be re-expressed as follows.

    FOR $b IN bib0/book
    WHERE notauthor("Buneman", $b) RETURN
      $b
==> <book year="2001" isbn="1-XXXXX-YYY-Z">
      <title>XML Query</title>
      <author>Fernandez</author>
      <author>Suciu</author>
    </book>
:   Book*

Note that a function declaration includes the types of all its arguments and the type of its result. This is necessary for the type system to guarantee that applications of functions are type correct.

In general, any number of functions may be declared at the top-level. The order of function declarations does not matter, and each function may refer to any other function. Among other things, this allows functions to be recursive (or mutually recursive), which supports structural recursion, the subject of the next section.

Functions make XQuery extensible. We have seen examples of built-in functions (sort and distinct-value) and examples of user-defined functions (notauthor). In addition to built-in and user-defined functions, XQuery could support externally defined functions, i.e., functions that are not defined in XQuery itself, but in some external language. This would make special-purpose implementations of, for example, full-text search functions available in XQuery. We discuss support for externally defined functions in [Issue-0009:  Externally defined functions].

2.19 Structural recursion

XML documents can be recursive in structure, for example, it is possible to define a part element that directly or indirectly contains other part elements. In XQuery, we use recursive types to define documents with a recursive structure, and we use recursive functions to process such documents. (We can also use mutually recursive functions for more complex recursive structures.)

For instance, here is a recursive type defining a part hierarchy.

    TYPE Part = Basic | Composite
    TYPE Basic = 
      ELEMENT basic (
        ELEMENT cost (xs:integer)
      )
    TYPE Composite = 
      ELEMENT composite (
        ELEMENT assembly_cost(xs:integer)
        ELEMENT subparts (Part+)
      )

And here is some sample data.

    LET $part0 :=
      <composite>
        <assembly_cost>12</assembly_cost>
        <subparts>
          <composite>
            <assembly_cost>22</assembly_cost>
            <subparts>
              <basic><cost>33</cost</basic>
            </subparts>
          </composite>
          <basic><cost>7</cost</basic>
        </subparts>
      </composite> : Part
    RETURN ...

Here vertical bar (|) is used to indicate a choice between types: each part is either basic (no subparts), and has a cost, or is composite, and includes an assembly cost and subparts.

We might want to translate to a second form, WHERE every part has a total cost and a list of subparts (for a basic part, the list of subparts is empty).

    TYPE Part2 =
      ELEMENT part (
        ELEMENT total_cost (xs:integer),
        ELEMENT subparts (Part2*)
      )

Here is a recursive function that performs the desired transformation. It uses a new construct, the typeswitch expression.

    DEFINE FUNCTION convert(Part $p) RETURNS Part2 {
      TYPESWITCH ($p) AS $x
        CASE Basic RETURN
          <part>
            <total_cost> { $x/cost/data() } </total_cost>
            <subparts/>
          </part>
        CASE Composite RETURN 
          LET $s := (FOR $y IN $x/subparts/* RETURN convert($y)) 
          RETURN
          <part>
              <total_cost>
                { $q/assembly_cost/data() + 
                  sum($s/total_cost/data()) } 
              <total_cost>
              <subparts> { $s } </subparts>
          </part>
        DEFAULT RETURN ERROR
    }

Each branch of the typeswitch expression is labeled with a type, Basic or Composite. The evaluator checks the type of the value of $p at query-evaluation time, i.e., run time, and evaluates the corresponding branch. If the first branch is taken then $x is bound to the value of $p, and the branch returns a new part with total cost the same as the cost of $x, and with no subparts. If the second branch is taken, then $x is bound to the value of $p. The function is recursively applied to each of the subparts of $x, giving a sequence of new subparts $s. The branch returns a new part with total cost computed by adding the assembly cost of $x to the sum of the total cost of each subpart in $s, and with subparts $s.

One might wonder why $x is required, since it has the same value as $p. The reason why is that $p and $x have different types.

    $p : Part
    $x : Basic       -- in the first branch
    $x : Composite   -- in the second branch

The type of $x is more precise than the type of $p, because which branch is taken depends upon the type of value in $p.

Applying the query to the given data gives the following result.

    convert($part0)
==> <part>
      <total_cost>74</total_cost>
      <subparts>
        <part>
          <total_cost>55</total_cost>
          <subparts>
            <part>
              <total_cost>33</total_cost>
              <subparts/>
            </part>
          </subparts>
        </part>
        <part>
          <total_cost>7</total_cost>
          <subparts/>
        </part>
      </subparts>
    </part>
: Part2

Of course, a typeswitch expression may be used in any query, not just in a recursive one.

2.20 Functions for all well-formed documents

[XML Schema : Formal Description] defines a ``root'', or most general type, for the four kinds of schema components: elements, attributes, simple types, and complex types. They are named xs:AnyElement, xs:AnyAttribute, xs:AnySimpleType, and xs:AnyComplexType, respectively. The type xs:AnySimpleType stands for the most general simple type. All built-in primitive types (like xs:integer or xs:string) and lists of simple types are subtypes of it. The built-in simple types are listed in [3.4 Atomic simple types]. The remaining schema components are defined as follows:

TYPE xs:AnyTree        = xs:AnySimpleType 
                        | xs:AnyElement 
                        | xs:AnyAttribute
TYPE xs:AnyAttribute   = ATTRIBUTE *:* (xs:AnySimpleType)
TYPE xs:AnyElement     = ELEMENT *:* (xs:AnyComplexType)
TYPE xs:AnyComplexType = xs:AnyAttribute*, 
                         ((xs:AnyElement | xs:string)* | xs:AnySimpleType)
TYPE xs:AnyType        = (xs:AnyTree)*

The type xs:AnyTree denotes any simple type, element, or attribute. The type xs:AnyAttribute stands for the most general attribute type, which may have any name, and its content must have type xs:AnySimpleType, i.e., it may contain simple values, but no elements. The type xs:AnyElement stands for the most general element type, which may have any name, and its content must be a complex type. The type xs:AnyComplexType stands for the most general complex type, which is any sequence of attributes followed by any sequence of elements or strings or by any simple type. Strings are permissible in a complex type because an element may contain mixed content, i.e., character data interleaved with other elements. Finally, xs:AnyType is a sequence of any tree.

In particular, our earlier data also has type xs:AnyElement.

    $book0 : xs:AnyElement
==> <book year="1999" isbn="1-55860-622-X">
      <title>Data on the Web</title>
      <author>Abiteboul</author>
      <author>Buneman</author>
      <author>Suciu</author>
    </book>
:   xs:AnyElement

A specific type can be indicated for any expression in the query language, by writing a colon and the type after the expression.

As an example of a function that can be applied to all well-formed documents, we define a recursive function that converts any XML data into HTML. We first give a simplified definition of HTML.

    TYPE HTML_body =
      ( xs:AnySimpleType
      | ELEMENT b(HTML_body)
      | ELEMENT ul ((ELEMENT li (HTML_body))*)
      ) *

An HTML body consists of a sequence of zero or more items, each of which is either a simple value, or a b element, where the content is an HTML body, or an ul element, where the children are li elements, each of which has as content an HTML body.

Now, here is the function that performs the conversion.

    
DEFINE FUNCTION html_of_xml( xs:AnyTree $x ) RETURNS HTML_Body {
  TYPESWITCH ($x) AS $z
    CASE xs:AnySimpleType RETURN $z
    CASE xs:AnyAttribute RETURN 
      <b> { name($z) } </b>,
      <ul> { FOR $y IN $z/data() RETURN <li>{ html_of_xml($y) }</li> } </ul>
    CASE xs:AnyElement RETURN 
      <b> { name($z) } </b>,
      <ul>{ FOR y IN $z/@* RETURN <li>{ html_of_xml($y) }<li> } </ul>,
      <ul>{ FOR y IN $z/* RETURN <li>{ html_of_xml($y) }</li> } </ul> 
    DEFAULT RETURN ERROR
}

The first branch of the typeswitch expression checks whether the value of $x is a subtype of xs:AnySimpleType, and if so then $z is bound to that value, so if this branch is taken then $z is the same as $x, but with a more precise type (it must be a simple type, not an element). This branch returns the scalar.

The second branch checks whether the value of $x is a subtype of xs:AnyAttribute. As before, $z is the same as $x but with a more precise type (it must be an attribute, not a scalar). This branch returns a b element containing the name of the attribute, and a ul element containing one li element for each value of the attribute. The function is recursively applied to get the content of the li element. The last branch is analogous to the second, but it matches an element instead of an attribute, and it applies html_of_xml to each of the element's attributes and children.

Applying the query to the book element above gives the following result.

    html_of_xml($book0)
==> <b>book</b>
    <ul> 
      <li><b>year</b><ul><li>1999</li></ul></li>
      <li><b>isbn</b><ul><li>1-55860-622-X</li></ul></li>
      <li><b>title</b><ul><li>Data on the Web</li></ul></li>
      <li><b>author</b><ul><li>Abiteboul</li></ul></li>
      <li><b>author</b><ul><li>Buneman</li></ul></li>
      <li><b>author</b><ul><li>Suciu</li></ul></li>
    </ul>
:   HTML_Body

2.21 Top-level queries and XML results

A XQuery module consists of a sequence of top-level declarations, i.e., a namespace declaration, function declaration, or type declaration, followed by a query expression. The order of top-level declarations is immaterial; all namespace, function, and type declarations may be mutually recursive.

The query expression is evaluated in the environment specified by all of the declarations. We have already seen examples of type, function, and namespace declarations. An example of a top-level query is:

    html_of_xml(book0)

The result of a top-level query can be serialized into an XML document by the application in which XQuery is used.

3 XQuery Core Syntax

In this section, we present the grammar for XQuery's core expressions and types. Literals are in typewriter font. Terminal classes of literals are italicized and have the suffix 'literal', e.g., StringLiteral. Non-terminal symbols are italicized, e.g., Expr. In the grammar, the '|' operator denotes an alternative of two symbols; '*' denotes zero or more repetition of a symbol; and '?' denotes an optional symbol.

3.1 Expressions

[Figure 1]  contains the grammar for XQuery's core expressions. We define XQuery's typing rules on these core expressions in [4 Static Semantics : Type-Inference Rules].

---

NCName Variable ::= $u, $v, $w, ... StringLiteral ::= "", "a", ... NumericLiteral ::= 0, 1, 2, ... BooleanLiteral ::= true | false Literal ::= StringLiteral | NumericLiteral | BooleanLiteral QName ::= NCName | NCName:NCName Opeq ::= eq | node-equal | ne | lt | lteq | gt | gteq Oparith ::= + | - | * | mod | div Opcoll ::= union | except | intersect Opbool ::= and | or InfixOp ::= Opeq | Oparith | Opcoll | Opbool PrefixOp ::= + | - | not Expr ::= Literal   | Variable   | QName ( ExpSequence? )   | Expr InfixOp Expr   | PrefixOp Expr   | attribute QName ( Expr )   | ElementConstructor   | ExprSequence   | if (Expr) then Expr else Expr   | let Variable := Expr return Expr   | Expr : Type   | error   | for Variable in Expr return Expr   | Expr sortby Expr ascending | descending   | cast as Type ( Expr )   | typeswitch (Expr) as Variable CaseRules CaseRules ::= case Type return Expr CaseRules   | default return Expr ExprSequence ::= Expr (, ExprSequence)* ElementConstructor ::= <NameSpec/> | <NameSpec> EnclosedExpression </NameSpec> EnclosedExpression ::= { ExprSequence } NameSpec ::= QName | { Expr } TypeDecl ::= type NCName = Type ContextDecl ::= namespace NCName = StringLiteral | default namespace = StringLiteral FunctionDefn ::= define function QName ( ParamList? ) returns Type { Expr } ParamList ::= Type Variable (, Type Variable)* QueryModule ::= ContextDecl* TypeDecl* FunctionDefn* ExprSequence? QueryModuleList ::= QueryModule ( ; QueryModule )*

---

Figure 1: XQuery Core Expression Syntax

---

Many of the expressions that appear in the examples, for example Expr/*, do not appear in [Figure 1], because they are reducible to expressions in the core syntax. [6 XQuery Mapping to Core] defines the mapping for every XQuery expression into an equivalent expression in the core syntax.

3.2 Operators

In addition to the core syntax, XQuery has a set of operators and built-in functions. The binary and unary operators are enumerated in [Figure 1]. They include two equality operators, eq and nodeeq, defined in the [XQuery 1.0 and XPath 2.0 Data Model], and five inequality operators, lteq, lt, gteq, gt, and ne. We have not defined the semantics of all the binary operators in XQuery. In particular, it might be useful to define more than one type of equality over scalar and element values, or to define implicit coercions between values of related types. A joint task force on operators with members from the [XSLT 99], XML Schema, and XML Query working groups is chartered to define operators. XQuery will adopt the decisions of that group (See [Issue-0056:  Operators on Simple Types]).

3.3 Built-in functions

XQuery's built-in functions are either defined in [XQuery 1.0 and XPath 2.0 Data Model] or in a forthcoming document that defines operators and a library of functions for XQuery and XPath 2.0. In this document, the data model functions have no namespace prefix and the library functions have the namespace prefix xfo. Some of these functions require special static type rules; these are listed in [Figure 2] and [Figure 3]. [Figure 2] contains the constructor and accessor functions defined in the [XQuery 1.0 and XPath 2.0 Data Model]. The remaining built-in functions are listed in [Figure 3]. One benefit of having built-in functions is that more precise types can be given to these functions than to user-defined functions. The type rules for these functions appear in [4 Static Semantics : Type-Inference Rules].

---

attributes(Expr)	Returns attributes of element.
children(Expr)	Returns children of element.
comment(Expr)	Constructs a comment.
dereference(Expr)	Dereferences a node reference.
local-name(Expr)	Extracts local NCName of a node.
name(Expr)	Returns element or attribute's tag name.
namespace-uri(Expr)	Extracts URI namespace from a node.
parent(Expr)	Returns the parent of a node.
pcdata(Expr)	Constructs parsable character data from string argument.
processing-instruction(Expr, Expr)	Constructs a processing instruction.
ref(Expr)	Constructs a node reference.
string-value(Expr)	Returns string value of given node, as defined in [XPath].
typed-value(Expr)	Returns the simple typed value of an element or attribute.

---

Figure 2: Data Model Constructor and Accessor Functions

---

---

agg(Expr)	Aggregation functions, where agg is avg, count, min, max, sum.
descendent-or-self(Expr)	Returns given node and all its descendents in document order.
distinct-node(Expr)	Removes duplicate nodes from a sequence.
distinct-value(Expr)	Removes duplicate values from a sequence.
eop(Expr)	Equality/inequality functions,
	where eop is one of eq, neq, lt, lteq, gt, gteq.
index(Expr)	Pairs each element of an sequence with integer index.
xfo:node-before(Expr, Expr)	True if first argument is before second in document order.
xfo:node-equal(Expr, Expr)	Returns true if both expressions denote the same node.

---

Figure 3: Built-In Functions

---

3.4 Atomic simple types

The XQuery type system takes as given the built-in simple datatypes from XML Schema Part 2 [XML Schema Part 2]. We let b range over all built-in datatypes.

The built-in simple datatype AnySimpleType stands for the most general simple type, and all other primitive and simple types (like xs:integer or xs:string) are subtypes of it.

In [XML Schema Part 2], a simple datatype is either a primitive datatype, or is derived from another simple datatype by specifying a set of facets. A type hierarchy is induced between simple types by containment of facets. Note that lists of simple datatypes are specified using repetition and unions are specified using alternation, as defined in [3.5 Types]

For simplicity, the type syntax in this document does not provide any way to define datatypes with facets. Such types can be imported from XML Schema and may be referenced by a qualified name QName. We let p range over all built-in datatypes, lists of built-in datatypes, and imported simple types.

3.5 Types

[Figure 4]  contains the abstract syntax for XQuery's type system. This type syntax appears in the typing rules in [4 Static Semantics : Type-Inference Rules]. An XQuery type corresponds to a content group as defined in [XML Schema : Formal Description]. See [Issue-0088:  Align XQuery types with XML Schema : Formal Description.] for alignment issues between XQuery type syntax and [XML Schema : Formal Description].

---

type variable y     unit type u ::= p simple type     | ATTRIBUTE NameSet (t)     | ELEMENT NameSet (t)     | PROCESSING-INSTRUCTION     | COMMENT     | REFERENCE (t) type t ::= y type variable     | () empty sequence     | Ø empty choice     | u unit type     | t1 , t2 sequence, t1 followed by t2     | t1 & t2 interleaved product     | t1 | t2 choice, t1 or t2     | t min m max n repetition of t m to n times     | t * repetition of t 0 to * times     | t + repetition of t one to * times     | t ? repetition of t 0 to 1 times     | PIC (t)     | MIXED (t) bound m, n ::= natural number or * prime type q ::= u     | q | q expanded QName expQName ::= {anyURI}NCName names NameSet ::= QName | expQName | * | NCName:* | *:* | NameSet OR NameSet | NameSet DIFF NameSet | (NameSet)

---

Figure 4: Abstract Syntax for Types

---

---

*, +, ?, min m max n, |, &, ,,

---

Figure 5: Precedence of Type Operators (highest to lowest)

---

A unit type is is either a simple type, an attribute or element type with name in NameSet and content in t, a comment type, a processing-instruction type, or a node-reference type.

The empty sequence matches only the empty document; it is an identity for sequence and all. The empty choice matches no document; it is an identity for choice.

An interleaved product t1 & t2 is nodes in t₁ interleaved with nodes in t₂ The interleaved product (also known as the shuffle product) is a generalization of XML Schema's [XML Schema Part 1] allgroups. t₁ & t₂ matches any sequence that is an interleaving of a sequence that matches t₁ and a sequence that matches t₂. For example,

     (ELEMENT a(), ELEMENT b()) & ELEMENT c() =
	      ELEMENT a(), ELEMENT b(), ELEMENT c()
	  |   ELEMENT a(), ELEMENT c(), ELEMENT b()
	  |   ELEMENT c(), ELEMENT a(), ELEMENT b()

As another example, ELEMENT a()* & ELEMENT b() matches any sequence of ELEMENT a() and ELEMENT b() that has exactly one ELEMENT b().

Allgroups in XML Schema may only consist of global or local element declarations with lower bound 0 or 1, and upper bound 1. With these restrictions, an allgroup in XML Schema is equivalent to p₁min m₁ max 1 & ... & p_n min m_n max 1 where p_i are element declarations and 0 <= m_i <= 1.

The repetition type t min m max n denotes a sequence of at least m and at most n t. The bounds on a repetition type will be either a natural number (that is, either a positive integer or zero) or the special value *, meaning unbounded. We extend arithmetic to include * in the obvious way:

For technical reasons, we allow the lower bound of a repetition to be *. A repetition t min m max n is equivalent to the empty choice Ø if m > n or if m is *.

The type expression PIC(t) is a convenient shorthand for the type (PROCESSING-INSTRUCTION | COMMENT)* & t, that is, a type in which processing instructions and comments may be interleaved with nodes in type t. Similarly, the type expression MIXED(t) is a convenient shorthand for the type xs:AnySimpleType* & t.

A prime type is a unit type or a disjunction of prime types. Unit and prime types appear in several typing rules in [4 Static Semantics : Type-Inference Rules].

A wildcard expression ([XML Schema : Formal Description]) denotes a set of names. A name set is either a QName denoting the name with the given namespace prefix and local name; an expanded QName denoting the name with the given namespace uri and local name; *:* denoting any name in any namespace; NCName:* denoting any local name in namespace NCName; or * denoting any local name in the default namespace. A name set also consists of union of wildcards or difference of wildcards. We let NameSet range over name sets.

The abstract syntax for content groups in [XML Schema : Formal Description] and in the corresponding abstract syntax above is more permissive than XML Schema. For example, these grammars permit an attribute to contain arbitrarily complex content and for attributes and elements to be combined in arbitrary ways. In [XML Schema : Formal Description], syntactic categories are used to specify various subsets of types and to restrict how types may be combined. Syntactic categories can indicate, for example, that the content of an attribute should be a simple type and that the content of an element should consist of attributes followed by elements. These restrictions guarantee that errors in type construction can be caught during parsing of a query.

We also use syntactic categories to restrict how types may be constructed. In the concrete syntax for types, we capitalize non-terminal symbols. We first distinguish between type variables used to name attribute groups, element groups, and the content types of elements. Type variables correspond to component names in [XML Schema : Formal Description].

A simple type is either an atomic type, a choice of atomic types, or a list of atomic or choice types:

An attribute group defines the syntactic form of attributes: their content may only be a simple type and they are combined only with the interleaving operator, but not the sequence operator.

An element group contains elements with constant or wildcard names and they are combined in sequences, choices, interleavings, and repetitions.

The content type of an element is either a simple type, an attribute group, an element group, a sequence of an attribute group followed by an element group, or a content-type variable.

Finally, a type in an XQuery expression may be an attribute group, an element group, or a content type:

4 Static Semantics : Type-Inference Rules

XQuery's static semantics is presented as type inference rules, which relate XQuery expressions to types and and specify under what conditions an expression is well typed. The rules for typing expressions are described with an inference rule notation, which is used for describing type systems and semantics of programming languages. For a textbook introduction to type systems, see, for example, [Mitchell].

In inference notation, when all judgements above the line hold, then the judgement below the line holds as well. Here is an example of a rule used later on:

Data is the subset of expressions that consists only of literal constant, attribute, element, sequence, and empty-sequence expressions.

• Data₁ = <a>{ 1 }</a>

• Data₂ = <b>{ "two" }</b>

• t₁ = ELEMENT a (xs:integer)

• t₂ = ELEMENT b (xs:string).

Then since both these hold:

<a>{ 1 }</a>     : ELEMENT a (xs:integer)
<b>{ "two" }</b> : ELEMENT b (xs:string)

we may conclude that the following holds:

  <a>{ 1 }</a>, <b>{ "two" }</b>
: ELEMENT a (xs:integer), ELEMENT b (xs:string)

4.1 Relating data to types

The following type rules relate Data values to types. The next rule rules states that a literal NCName has the type xs:NCName. The following three rules are analogous for strings and double precision numbers.

Ed. Note: MF: Analogous rules are necessary for all the functions that construct Schema simple-typed values.

The next three rules are for attribute and element construction. The first rule states that if Data has type t, then the attribute expression attribute NCName Data has type ATTRIBUTE NCName (t). The subsequent rules are analogous for element expressions.

The next rule states that the empty sequence value always has the empty sequence type:

This rule was described above:

The rules above associate the most specific type possible with a Data value. The remaining rules in this section associate more general types with a Data value, which are necessary when the type system must determine whether a Data value with most specific type t is permissible when a value of type t' is expected. This occurs during type checking of a query.

The next two rules are also for attribute and element construction, but these rules specify more general types. The first rule states that if Data has type t, and NCName is in the set of names defined by the wildcard expression NameSet, then the given attribute expression also has type ATTRIBUTE NameSet (t). The subsequent rules are analogous for element expressions.

The next rule states that the sequence of one value with type t followed by a value with repetition type t min m max n has repetition type t min m+1 max n+1.

The next rule states that the empty sequence is a repetition of any type with lower bound 0:

4.2 Equivalences and subtyping

The symbol <: denotes the subtype relation. We write t₁<: t₂ if for every data Data such that |- Data : t₁, it is also the case that |- Data : t₂, i.e., is t₁ is a subtype of t₂. The subtyping relation is used in many of the type rules that follow. It is easy to see that the subtype relation <: is a partial order, i.e., it is reflexive, t <: t, and it is transitive, if t₁<: t₂and t₂<: t₃then t₁<: t₃. Here are some of the inequalities that hold:

Further, if QName <:_wild NameSet and t <: t', then

If t <: t' and m >= m' and n <= n' then

If t₁<: t₁' and t₂<: t₂' then

We write t₁= t₂ if t₁<:t₂ and t₂<: t₁. Here are some of the equalities that hold:

We also have that t₁<: t₂ if and only if t₁| t₂= t₂.

We define the intersection t₁ /\ t₂ of two types t₁ and t₂ to be the largest type t that is smaller than both t₁ and t₂. That is, t = t₁ /\ t₂ if t <: t₁ and t <: t₂ and if for any t' such that t' <: t₁ and t' <: t₂, we have t' <: t.

4.3 Environments

The type rules use an environment comprised of a type environment and a namespace environment, defined in [Figure 6].

---

T	in	TypeEnv = (Variable -> Type) U	Type environment
		(QName -> QName(Type1, ..., Typen) returns Type)
NS	in	NamespaceEnv = NCName -> anyURI	Namespace environment
G	in	Env = TypeEnv X NamespaceEnv	Static environment

---

Figure 6: Environments used in type-inference rules

---

The type environment T is a finite map from variables and function names to types.

Part of an attribute or element's type is its tag name, which is a QName. A QName contains a namespace prefix, whose meaning depends on the namespace environment NS, which is a finite map from namespace prefixes (NCNames) to namespace URIs. The namespace environment is modified by namespace declarations and by element constructors that contain namespace declarations.

To select the type-environment component of an environment, we use the notation T of G; similarly, we use NS of G to select the namespace environment.

We retrieve type information from the environment by writing T (Variable)= t to look up a variable, or by writing T(QName) = (QName(t₁, ..., t_n) returns t) to look up a function type. We write NS(NCName) = anyURI to look up a namespace prefix.

It is often necessary to modify an environment, for example, when defining variables or functions. The modification of one environment G by another G' is written G, G' and it denotes:

G, G' = ((T of G), (T' of G'); (NS of G), (NS' of G'))

The finite map f, g is the finite map with domain Dom f U Dom g, and values

  (f, g)(a) = if a in Dom g then g(a) else f(a)

The type checking starts with an empty type environment. As type checking proceeds, new variables are added to the type environment and new namespace prefixes are added to the namespace environment. For instance, when typing the query of [2.4 Iteration], variable $b will be typed with Book, and added in the environment. This will result in a new environment:

G' = G, $b : Book

4.4 Expressions

We write G |- Expr : t if in environment G the expression Expr has type t. Below are all the rules except those for for and typeswitch expressions, which are discussed in later subsections.

The following rule states that in any environment G, the literal NCName has the type xs:NCName. The two subsequent rules are analogous for strings and numerical values. For example, G |- 1 : xs:integer and G |- "two" : xs:string.

The next rule simply states the variable Variable has type t in environment G:

Part of an attribute or element's type is its tag name, which is a QName. Before computing the type of an attribute or element, we convert the attribute or element's QName into an expanded QName. The inference rule below converts a QName into an expanded QName by mapping its namespace prefix to a namespace URI. Later rules rely on this judgement to resolve the namespace prefixes that occur in the QNames of elements and attributes.

The next two rules are for attribute and element construction with a constant tag name. The first rule states that if Expr has type t, and that QName resolves to the given expanded QName, then the attribute expression ATTRIBUTE QName (Data) has type ATTRIBUTE expQName (t). The subsequent rules are analogous for element expressions.

Ed. Note: MF: (08-May-2001) The above rules do not handle namespace attributes in element constructors, e.g., <foo:bar xmlns:foo="http://www.foo.com/foo.xsd">. These need to be added. In mapping from XQuery to core, all namespace attributes should occur before other attributes.

The next rule is for element construction in which the tag name is computed. The built-in function make-attribute is used to construct an attribute with a computed tag; its typing rule appears in [4.6 Built-in functions]. The rule states that if Expr₂ has type t, then the element expression with computed tag Expr₁ has type ELEMENT *:* (t).

Ed. Note: MF: Note that the types are less precise than in Algebra, which supported name expressions and wildcard types. This probably makes the 80-20 cut.

The following two rules are analogous to the sequence and empty sequence rules in [4.1 Relating data to types].

Note that in the type rule for a conditional expression, the result type is the choice (t₂|t₃).

A let expression extends the type environment G by mapping Variable to type t. Note that Expr₂, the body of the let expression, is typed in the extended environment, and the type of the entire let expression is t₂.

The next rule is for function application. In a function application, the type of each actual argument to the function must be a subtype of the corresponding formal argument to the function, i.e., it is not necessary for the actual and formal types to be equal.

The next rule states that it is always permissible to explicitly type an expression with a type t' that is a supertype of the expression's type t. In programming-language terminology, this operation is sometimes called an ``upcast''.

The cast operator converts the type of an expression to the given atomic simple type.

Ed. Note: MF: the relationship between p and p' depends on operator work.

The error expression always has the empty choice type.

4.5 Operators

A joint task force on operators with members from the XSLT, XML Schema, and XML Query working groups is chartered to define the operators for XQuery and XPath 2.0. The complete set of operators will be defined in a forthcoming document by that group, so it is not possible to give the typing rules for all operators here. (See [Issue-0056:  Operators on Simple Types]). In general, however, arithmetic operators will have a type rule such as the following, in which t₁ and t₂ are numeric types and appropriate type conversions exist between the two:

Equality and inequality operators are typed similarly.

Boolean operators require that their subexpressions be boolean expressions.

The type rules for the collection operators, Op_coll, are given in [4.7 Typing unordered expressions].

4.6 Built-in functions

The following type rules define the input and output types for built-in functions.

The next two rules are for comment and processing instruction constructors.

In the core syntax, all character-data literals are expressed using the built-in pcdata (parsable character data) function. The type of PCDATA is always xs:AnySimpleType.

Attributes with computed tag names are constructed by the make-attribute. This rule states that if Expr₂ has type t, then the attribute expression with computed tag Expr₁ has type ATTRIBUTE *:* (t).

The name of an attribute or element always has type xs:QName:

The attributes and children accessors only apply to values with element type.

The next two rules are for name expressions: they extract the constituent parts of a name.

The next rule is for the parent function, which may be applied to any unit type:

The next two rules are for the reference constructor and dereference function. Note that ref requires that its argument have a unit type.

The next rule is for the string-value of a unit value.

The accessor typed-value returns the simple typed value of an attribute or element. An attribute always contains a simple typed value, therefore typed-value simply returns the attribute's typed content. An element may contain a simple-typed value or a complex-typed value. The second and third rules below distinguish between these two cases.

4.7 Typing unordered expressions

The built-in functions index and unordered and the operator sortby disregard the relative order of components in their input type.

For example, consider the following.

    index (children (book0))
==> (<q:pair><q:fst>1</q:fst>
            <q:snd><q:ref><title>Data on the Web</title></q:ref></q:snd></q:pair>,
     <q:pair><q:fst>2</q:fst>
            <q:snd><q:ref><author>Abiteboul</author></q:ref></q:snd></q:pair>,
     <q:pair><q:fst>3</q:fst>
            <q:snd><q:ref><author>Buneman</author></q:ref></q:snd></q:pair>,
     <q:pair><q:fst>4</q:fst>
            <q:snd><q:ref><author>Suciu</author></q:ref></q:snd></q:pair>,
     <q:pair><q:fst>5</q:fst>
            <q:snd><q:ref><year>1999<year></q:ref></q:snd></q:pair>)

By nesting the children of book0 under snd the original sequence of title, author+, year gets lost. The snd element can contain either a title, an author, or a year. To compute a meaningful type for this expression, we need to find a type q, m, and n such that

 children(book0) : q min m max n 

and then the type is given by

    index(children(book0)) : 
    ELEMENT q:pair(
      ELEMENT q:fst (xs:integer),
      ELEMENT q:snd (REFERENCE (ELEMENT author (q)))
    ) min m max n

In the case of books, the values of q are:

ELEMENT title (xs:string)  | 
ELEMENT author (xs:string) 

the value of m is three (because there will be one title, at least one author, and one year element) and the value of n is * (because there may be any number of author elements).

We call a type like q a prime type. In general, it may contain scalar, attribute, element, choice, and empty choice types, but it will not contain repetition, sequence, or empty sequence types (except, perhaps, within an element or attribute type). The definition of prime types appears in [Figure 4].

---

factor (p) = p min 1 max 1 factor (ELEMENT NameSet (t)) = ELEMENT NameSet (t) min 1 max 1 factor (ATTRIBUTE NameSet (t)) = ATTRIBUTE NameSet (t) min 1 max 1 factor (t1 , t2) = (q1| q2) min m1+ m2 max n1+ n2 where qi min mi max ni = factor (ti) factor (t1 & t2) = (q1| q2) min m1+ m2 max n1+ n2 where qi min mi max ni = factor (ti) factor (t1| t2) = (q1| q2) min (min m1 m2) max ( max n1 n2) where qi min mi max ni = factor (ti) factor (t min m max n) = q min m · m' max n' · n where q min m' max n' = factor (t) factor (()) = Ø min 0 max 0 factor (Ø) = Ø min * max 0

---

Figure 7: Definition of factoring

---

The factor function, as shown in [Figure 7], converts any type t to a type of the form q min > max n, where t <: q min > max n, so that any value that has type t also has type q min m max n. For example,

factor (ELEMENT title (xs:String), 
        ELEMENT author (xs:String) min 1 max *, 
        ELEMENT year (xs:integer)) = 

  (ELEMENT title (xs:string) | 
   ELEMENT author (xs:string) | 
   ELEMENT year(xs:integer)) min 3 max *

We can see here that the factored type is less specific than the unfactored type. For convenience we write q min m max n = factor (t), but one should actually think of the function as returning a triple consisting of a prime type q and two bounds m and n.

Just as factoring a number yields a product of prime numbers, factoring a type yields a repetition of prime types. Further, the result yielded by factoring is in some sense optimal. If q min m max n = factor (t) then t <: q min m max n and for any q', m', and n' such that t <: q'min m max n' we have that q <: q' and m >= m' and n <= n'. Also, if t = t', then factor (t) = factor (t'). In particular, the choice of the lower bound * for factor (Ø) guarantees that factor (t) = factor (t | Ø), since m min * = m.

Using factor, we can type index, sortby, unordered and the union, difference, and intersection operations. Note that factor is only used by the type inference rules; it is not part of XQuery expressions.

The type rule for index requires that its argument be a factored type. The second expression above the judgement line converts t into a factored type.

The types of aggregated expressions must be factored, and their prime type must be a numeric type.

The sortby operator returns the factor of its input type.

Ed. Note: MF, Oct 23/2000: This definition assumes that the equality operator on t₂ is defined. An alternative is requiring Expr₂ to have xs:AnySimpleType, but that seems too restrictive.

The distinct-node function removes all duplicate nodes from its input.

Ed. Note: PF (Jan 29, 2000): a more accurate lower bound may be derived by counting the disjoint constituent types of q. But this is probably too complex.

The distinct-value function removes all duplicate values from its input. The typing rule is analogous to that of distinct-node, except the lower bound m can be at most one.

Similar to distinct-value and distinct-node, the intersect and except operators need to set the lower bound of the cardinality of the input type to 0. The upper bound of the cardinality of the intersection of two types can be at most the minimum of upper bounds of their individual cardinalities.

The unordered function ignores the order of the items in its sequence argument, therefore its type is also a factored type.

4.8 Iteration expressions

The typing of for expressions is rather subtle. We give an intuitive explanation first and then the detailed typing rules below.

A unit type is defined in [Figure 4]; it is either an simple type, an attribute or element type with a constant or wildcard name, a comment, or a processing instruction. A for expression

for Variable in Expr₁ return Expr₂

is typed as follows. First, one finds the type of expression Expr₁. Next, for each unit type in this type one assumes the variable Variable has the unit type and one types the body Expr₂. Note that this means we may type the body of Expr₂ several times, once for each unit type in the type of Expr₁. Finally, the types of the body Expr₂ are combined, according to how the types were combined in Expr₁. That is, if the type of Expr₁ is formed with sequencing, then sequencing is used to combine the types of Expr₂, and similarly for choice or repetition.

For example, consider the following expression, which selects all author elements from a book.

    for $c in children($book0) return
      typeswitch ($c)
        case $a : ELEMENT author(xs:AnyType) return $a
        default return ()

The type of children(book0) is

ELEMENT title(xs:String), ELEMENT year(xs:integer), ELEMENT author(xs:string)+

This is composed of three unit types, and so the body is typed three times.

The three result types are then combined in the same way the original unit types were, using sequencing and iteration.

(), (), ELEMENT author(xs:string)+

as the type of the iteration, and simplifying yields

ELEMENT author(xs:string)+

as the final type.

As a second example, consider the following expression, which selects all title and author elements from a book, and renames them.

  for $c in $book0/* return
    typeswitch ($c) 
      case ELEMENT title (xs:string)  return 
           <titl> { t/data() } </titl>
      case ELEMENT year (xs:integer)  return 
           ()
      case ELEMENT author (xs:string) return 
           <auth> { a/data() } </auth>
      default return ERROR

Again, the type of book0/* is

  ELEMENT title(xs:string), ELEMENT year(xs:integer), ELEMENT author(xs:string)+

This is composed of three unit types, and so the body is typed three times.

The three result types are then combined in the same way the original unit types were, using sequencing and iteration. This yields

 ELEMENT titl(xs:string), (), ELEMENT auth(xs:string)+

as the type of the iteration, and simplifying yields

 ELEMENT titl(xs:string), ELEMENT auth(xs:string)+

as the final type. Note that the title occurs just once and the author occurs one or more times, as one would expect.

As a third example, consider the following expression, which selects all basic parts from a sequence of parts.

  for $p in $part0/subparts/* return
    typeswitch ($p)
      case Basic     return $b
      case Composite return ()
      default return ERROR

The type of part0/subparts/* is

    (Basic | Composite)+

This is composed of two unit types, and so the body is typed two times.

The two result types are then combined in the same way the original unit types were, using sequencing and iteration. This yields

    (Basic | ())+

as the type of the iteration, and simplifying yields

    Basic*

as the final type. Note that although the original type involves repetition one or more times, the final result is a repetition zero or more times. This is what one would expect, since if all the parts are composite the final result will be an empty sequence.

In this way, we see that for expressions can be combined with typeswitch expressions to select and rename elements from a sequence, and that the result is given a sensible type.

In order for this approach to typing to be sensible, it is necessary that the unit types can be uniquely identified. However, the type system given here satisfies the following law.

 ELEMENT a (t1 | t2) = ELEMENT a (t1) | ELEMENT a (t2)

This has one unit type on the left, but two distinct unit types on the right, and so might cause trouble. Fortunately, our type system inherits an additional restriction from XML Schema: we insist that the regular expressions can be recognized by a top-down deterministic automaton. In that case, the regular expression must have the form on the left, the form on the right is outlawed because it requires a non-deterministic recognizer. With this additional restriction, there is no problem.

The method of translating projection to iteration described in the previous section combined with the typing rules given here yield optimal types for projections, in the following sense. Say that variable x has type t, and the projection x / a has type t'. The type assignment is sound if for every value of type t, the value of x / a has type t'. The type assignment is complete if for every value y of type t' there is a value x of type t such that x / a = y. In symbols, we can see that these conditions are complementary.

Any sensible type system must be sound, but it is rare for a type system to be complete. But, remarkably, the type assignment given by the above approach is both sound and complete.

The type rule for for expressions uses the following auxiliary judgement. We write G |- for Variable : t return Expr : t', if in environment G when the bound variable Variable of an iteration has type t then the body Expr of the iteration has type t'.

Given the above rules, the type rules for for expressions are immediate.

4.9 Typeswitch expressions

The typing of typeswitch expressions is closely related to the typing of for expressions. Due to the typing rules of for expressions, it is possible that the body of an iteration is checked many times. Thus, when a typeswitch expression is checked, it is possible that quite a lot is known about the type of the expression being matched, and one can determine that only some of the clauses of the typeswitch apply. The definition of typeswitch uses the auxiliary judgements to check whether a given clause is applicable.

We write G |- case Variable : t return Expr : t', if in environment G, the Variable of the typeswitch has type t, then the body Expr of case has type t'. Note the type of the body is irrelevant if t = Ø.

We write G |- t <: t' default return Expr: t'' if in environment G when t <: t' does not hold, then the body Expr of the typeswitch expression's default return clause has type t''. Note that the type of the body is irrelevant if t < t'.

Given the above, it is straightforward to construct the typing rule for a typeswitch expression. Recall that we write t /\ t' for the intersection of two types.

4.10 Typing descendent-or-self

The built-in function DESCENDENT-OR-SELF(expr) implements the descendent-or-self axis of XPath, and is used to express the sematics of the // operator. For example, consider the following type declaration:

    TYPE Part = Basic | Composite
    TYPE Basic =
      ELEMENT basic (
        ELEMENT cost (xs:integer)
      )
    TYPE Composite =
      ELEMENT composite (
        ELEMENT assembly_cost (xs:integer)
        ELEMENT subparts (Part+)
      )

If $v has type Part, the XPath expression $v//basic would retrieve all basic parts. We would rewrite this query into the core language as follows:

   for $x in descendent-or-self($v) return
     typeswitch ($x) as $z
       case ELEMENT basic(xs:AnyType) return $z
       default return ()

The type of descendent-or-self($v) is

  (ELEMENT basic (
       ELEMENT cost (xs:integer)
     )
   | ELEMENT cost (xs:integer)
   | ELEMENT composite (
       ELEMENT assembly_cost (xs:integer)
       ELEMENT subparts (Part+)
     )
   | ELEMENT assembly_cost ( xs:integer )
   | ELEMENT subparts ( Part+)
	| xs:integer
   ) min 3 max *

The lower bound of 3 indicates that descendent-or-self($v) returns at least three nodes, ELEMENT basic (...), ELEMENT cost (...), and xs:integer, which is what happens when $v is bound to a single element of type Basic. Based on this type, the type of $v//basic is

   ELEMENT basic (
	  ELEMENT cost (xs:integer)) min 0 max *

On the other hand, the type of $v//part is (), the empty sequence, because no part element appears in the type Part. (An expression with type () typically indicates a programming error, unless the expression is () itself.)

The typing of descendent-or-self loses all information about the relative ordering of the subparts. For instance, in descendent-or-self($v) it is always the case that a basic element is immediately followed (in document order) by a cost element, but this is not reflected in the type above.

There are two reasons why information about order is not retained.

First, there may exist two locally declared elements, e.g., ELEMENT foo(type1) and ELEMENT foo(type2), with the same name but different content-type. Maintaining their relative order at type level would generate the invalid type ELEMENT foo(type1) ... ELEMENT foo(type2), whereas ELEMENT foo(type1) | ELEMENT foo(type2) can be transformed to the valid type ELEMENT foo( type1 | type2).

Second, for some recursive types, maintaining the relative order of elements leads to a context-free type. For example, with

   TYPE type1 = ELEMENT a (type1 min 0 max 1), ELEMENT b ()

the type of descendents would need to be the context-free type

   TYPE type1' = ELEMENT a (type1 min 0 max 1), type1', ELEMENT b ()

but there is no equivalent regular type expressible in our system.

In principle, DESCENDENT-OR-SELF(expr) could be expressed as a recursive user defined function:

   DEFINE FUNCTION descendent-or-self (xs:AnyTree $x) 
          RETURNS (xs:AnyElement | xs:AnyScalar) min 0 max * {
     TYPESWITCH ($x)
        CASE (Comment|PI|AnyAttribute) RETURN ()
        DEFAULT RETURN 
          ($x, FOR $z IN children($x) RETURN descendent-or-self($z))
   }

However, this loses far too much type information. With this definition and the translation above the type of $v//basic is

  ELEMENT basic(xs:AnyType) min 0 max *

rather than

  ELEMENT basic(ELEMENT cost(xs:integer)) min 0 max *

Similarly, the type of $v//part is (ELEMENT part (AnyType) min 0 max *) rather than (), losing the chance to uncover a type error.

The rule for typing descendent-or-self(expr) is as follows.

This uses the function recfactor defined in [Figure 8]. The function recfactor() is similar to factor(), but it applies to all the descendents of a node.

To be precise, recfactor(t; E) takes a type t and a choice of type variables E. The argument E is a factoring environment: initially the empty choice Ø, it collects all the type variables encountered so far in a recursive traversal of the type. If t is a type in which all elements have empty content models, then recfactor(t; Ø) = factor(t).

---

recfactor (p; E) = p min 1 max 1 recfactor (ELEMENT NameSet (t); E) = (ELEMENT NameSet (t) | q) min m + 1 max n + 1) where q min m + 1 n + 1 = recfactor (t; E) recfactor (ATTRIBUTE NameSet (t); E) = Ø min 0 max 0 recfactor (t1 , t2; E) = (q1| q2) min m1+ m2 max n1+ n2 where qi min mi max ni = recfactor (ti; E) recfactor (t1 & t2; E) = (q1| q2) min m1+ m2 max n1+ n2 where qi min mi max ni = recfactor (ti; E) recfactor (t1| t2; E) = (q1| q2) min (min m1 m2) max ( max n1 n2) where qi min mi max ni = recfactor (ti; E) recfactor (t min m max n) = q min m · m' max n' · n where q min m' max n' = recfactor (t; E) recfactor ((); E) = Ø min 0 max 0 recfactor (Ø; E) = Ø min * max 0 recfactor (X; E) = recfactor (def(X);E | X) if not X <: E recfactor (X; E) = factor (def(X)) min * max * if X <: E

---

Figure 8: Definition of recursive factoring

---

4.11 Top-level declarations and query expressions

We write G |- QueryModule if in environment G, the query module QueryModule is well-typed.

Context declarations are always well typed. Below, they have the effect of updating the namespace environment.

A type declaration is always well typed:

A function declaration is well-typed if in the environment extended with the type assignments for its formal variables, its body is well-typed.

The function static-env constructs an environment by extracting type assertions and namespace mappings from top-level declarations. It constructs a two part environment: the first part is the type environment, T, and the second part is the namespace environment, NS.

Note that the default namespace is represented in the namespace environment by the empty string.

We write |- QueryModule if each declaration and expression in the query module is well typed.

5 Dynamic Semantics : Value-Inference Rules

XQuery's dynamic, or operational, semantics is presented as value inference rules. The value inference rules are similar to the type inference rules in [4 Static Semantics : Type-Inference Rules], but they relate expressions to values or semantic objects. XQuery's semantic objects are defined in the [XQuery 1.0 and XPath 2.0 Data Model]. An operational semantics specifies the order in which an XQuery expression is evaluated and guarantees that every expression can be reduced to a simple semantic object. XQuery's dynamic semantics is modeled on the dynamic semantics presented in [Milner].

5.1 Semantic objects

---

ERROR a in SimpleValue n in Node u in UnitValue = SimpleValue U Node s in Sequence<SimpleValue | Node> v in Values = Sequence<SimpleValue | Node> U {ERROR} sc in SchemaComponent

---

Figure 9: Semantic objects

---

There are five categories of values in [XQuery 1.0 and XPath 2.0 Data Model]: error, simple values, nodes, sequences, and schema components. There is a single error value, named ERROR. Simple values are the union of all the value spaces of XML Schema simple types. A node is one of eight node kinds: element, attribute, namespace, comment, processing-instruction, text, and reference. A unit value is the union of all simple values and nodes; a unit value is an instance of the unit type [Figure 4].

A sequence is an ordered collection of nodes, simple values, or any mixture of nodes and simple values. A sequence cannot be a member of a sequence. An important characteristic of the data model is there is no distinction between a unit value (i.e., a node or a simple value) and a singleton sequence containing that value, i.e., a unit value is equivalent to a singleton sequence containing that value and vice versa.

Value is the class of values that includes all sequences and ERROR.

A schema component represents the type of element nodes, attribute nodes, and simple values.

All the above classes, except ERROR, are infinite sets.

[Figure 10] lists several basic functions from [XQuery 1.0 and XPath 2.0 Data Model] used in the dynamic semantics.

---

append		Construct a sequence from two or more sequences
empty-sequence		Constructs the empty sequence.
empty		Returns true if argument is empty sequence, otherwise false.
head		Returns the first node in a non-empty sequence
tail		Returns items in a sequence excluding its first item.
schema-component		Returns the schema component representing its type argument

---

Figure 10: Functions used in dynamic semantics

---

Ed. Note: MF : (Jan-15-2001) To define the sort expression completely, we need to specify what basic sort operators are available.

5.2 Environments

The value inference rules use an environment, defined in [Figure 11], comprised of a static environment, a value environment, and a function environment.

---

G			Static environment
VE	in	ValueEnv = Variable -> Value	Value environment
FE	in	FuncEnv = QName -> (Expr X Variable*)	Function environment
E	in	Env = StaticEnv X ValueEnv X FuncEnv

---

Figure 11: Environments used in value-inference rules

---

The static environment G is defined by the static type rules [4 Static Semantics : Type-Inference Rules]. The value environment VE is a finite map from variables to values. The function environment FE is a finite map from function names to pairs containing an expression that is the body of the function and a list of free variables that are the function's formal arguments. An environment E is a tuple containing a static enviroment, a value environment, and a function environment.

In the value-inference rules, we use the same notation to select an environment and to lookup values in an environment as used in [4 Static Semantics : Type-Inference Rules].

To select the static-environment component of an environment, we use the notation G of E; similarly, we use VE of E to select the value environment and FE of E for the function environment.

We look up the type of a variable by writing (G of E)(Variable) = t, and we write (VE of E)(Variable) = v to look up the value of a variable or (FE of E)(QName) = f to look up a function.

It is often necessary to modify an environment, for example, when defining variables or functions. The modification of one environment E by another E' is written E, E' and it denotes:

E, E' = ((G of E), (G' of E'); (VE of E), (VE' of E'); (FE of E), (FE' of E'))

The finite map f, g is the finite map with domain Dom f U Dom g, and values

  (f, g)(a) = if a in Dom g then g(a) else f(a)

5.3 Expressions

Each rule of the dynamic semantics are inferences among sentences of the form: E |- phrase => v, where E is an environment, phrase is a phrase in the core syntax [Figure 1], and v is a semantic object.

As in [4 Static Semantics : Type-Inference Rules], when all judgements above the line of an inference rule hold, then the judgement below the line holds as well. The following three rules state that in any environment, a string, numeric, or boolean literal reduces to the value it denotes. The XQuery/XPath 2.0 function library provides constructors for all simple-typed values. Those constructors are used here:

The next rule determines the value of a variable, which is simply the variable's value in the current value environment VE:

The next rule constructs an attribute node from its name and value sub-expressions. This is the first rule that uses the static type environment: the run-time type schema-component(t) of the attribute is obtained from the type environment G.

The next rule constructs an empty element.

The following rule constructs an element from its name and children sub-expressions. The element constructor in [XQuery 1.0 and XPath 2.0 Data Model] requires that all children be nodes, which means that any simple-typed value in the element's sequence of child expressions must be converted to a text node before applying the constructor. The auxilliary function simple-to-text-node defined below performs this conversion.

define function simple-to-text-node(xs:AnyTree* $s) returns xs:AnyTree* {
  for $v in $s return
    typeswitch ($v)
    case xs:AnySimpleType return text-node(string-value($v))
    default return $v
}

Ed. Note: PF: Do we need to concatenate consecutive text-nodes ? MF: The element constructor should do this.

The next rule constructs a sequence.

We note here that in the [XQuery 1.0 and XPath 2.0 Data Model], sequences are always ``flat'', i.e., they do not contain other sequences.

The next three rules construct the union, difference, and intersection of two sequences. The order of items in the resulting sequence is non-deterministic.

The next rule constructs the empty sequence.

The next rule evaluates a conditional expression. If the conditional's boolean expression Expr₁ evaluates to true, Expr₂ is evaluated and its value is produced. If the conditional's boolean expression evaluates to false, Expr₃ is evaluated and its value is produced.