The XML Query Algebra

W3C Working Draft 04 December 2000

This version:

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

Latest version:

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

Editors:

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

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

---

Abstract

This document introduces the XML Query Algebra as a formal basis for an XML query language.

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. 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 XML Query Algebra and to elicit feedback on its current state. The XML Query Working Group feels it has made good progress on this document but this is still a work in progress and is liable to change in future versions. A number of important issues are still open - see also [B.3.1 Open Issues]. 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/).

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 proposes an algebra for XML Query.

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, 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, the algebra is used to give a semantics for the query language, so the operations of the algebra should be well-defined. Second, the algebra is used to support query optimization, so the algebra should possess a rich set of laws. Our algebra is powerful enough to capture the semantics of many XML query languages, and 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 compile time and to support query optimization. DTDs and XML Schema can be thought of as providing something like types for XML. The XML Query algebra uses a simple type system that captures the essence of [XSchema1]. The type system is close to that used in XDuce [HP2000]. On this basis, the XML Query algebra is statically typed. This allows to determine and check the output type of a query on documents conforming to an input type at compile time rather than at runtime. Compare this to the situation with an untyped or dynamically typed query language, where each individual output has to be validated against a schema at runtime, and there is no guarantuee that this check will always succeed.

The document is organized as follows. A tutorial introduction is presented in [2 The Algebra by Example]. After reading the tutorial, the reader will have seen the entire algebra and should be able to write example queries. The components of the algebra are described in detail in [3 Algebra Components]. We present some equivalence and optimization laws of the algebra in [4.3 Laws]. Finally, we give the static typing rules for the algebra in [5 Type Rules]. Although it contains the most challenging material, we have tried to make the content as accessible as possible. Nonetheless, this section is not necessary for understanding or using the algebra, therefore the reader may skip this section. In [B.2 Issues list], we discuss open issues and problems.

In Appendix [A The XML Query Data Model], we give a formal mapping relating the algebra to the XML Query Data Model.

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

2 The Algebra by Example

This section introduces the main features of the algebra, using familiar 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 a XML Schema for such data:

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

This data and schema is represented in our algebra as follows:

    type Bib =
      bib [ Book{0, *} ]
    type Book =
      book [
        @year  [ Integer ] & 
        @isbn  [ String ],
        title  [ String ], 
        author [ String ]{1, *}
      ]
    let bib0 : Bib =
      bib [
        book [
          @year  [ 1999 ], 
          @isbn  [ "1-55860-622-X" ], 
          title  [ "Data on the Web" ], 
          author [ "Abiteboul" ], 
          author [ "Buneman" ], 
          author [ "Suciu" ]
        ], 
        book [
          @year  [ 2001 ], 
          @isbn  [ "1-XXXXX-YYY-Z" ], 
          title  [ "XML Query" ], 
          author [ "Fernandez" ], 
          author [ "Suciu" ]
        ]
      ] 

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

The Bib type corresponds to a single bib element, which contains a forest of zero or more Book elements. We use the term forest to refer to an sequence of (zero or more) attributes and elements. Every attribute or element can be viewed as a forest of length one.

The Book type corresponds to a single book element, which contains one year attribute and one isbn attribute, followed by one title element, followed by one or more author elements. The & operator, called an all group, 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 variable bib0 is bound to a literal XML value, which is the data model representation of the earlier XML document. The bib element contains two book elements.

The algebra 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 = 
        book [
          @year  [ 1999 ], 
          @isbn  [ "1-55860-622-X" ], 
          title  [ "Data on the Web" ], 
          author [ "Abiteboul" ], 
          author [ "Buneman" ], 
          author [ "Suciu" ]
        ]

2.2 Projection

The simplest operation is projection. The algebra uses a notation similar in appearance and meaning to path navigation in XPath. The following expression returns all author elements contained in book elements contained in bib0:

    bib0/book/author
==> author [ "Abiteboul" ], 
    author [ "Buneman" ], 
    author [ "Suciu" ], 
    author [ "Fernandez" ], 
    author [ "Suciu" ]
:   author [ String ] {0, *}
 

Note that in the result, the document order of author elements is preserved and that duplicate elements are also preserved.

The above example and the ones that follow have three parts. First is an expression in the algebra. 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{0, *}
    bib0/book/author : author [ String ]{0, *}
 

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 run-time value and its compile-time type. 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.

2.3 Atomic data

One may access atomic 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"
:   String {1, *}

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

    book0/@year/data()
==> 1999
:   Integer

This notation is similar to the use of text() in XPath. 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 do
      book [ b/author, b/title ]
==> book [
      author [ "Abiteboul" ], 
      author [ "Buneman" ], 
      author [ "Suciu" ], 
      title  [ "Data on the Web" ]
    ], 
    book [
      author [ "Fernandez" ], 
      author [ "Suciu" ], 
      title  [ "XML Query" ]
    ]
:   book [
      author[ String ]{1, *}, 
      title[ String ]
    ]{0, *} 

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{0, *}
    b                : Book
    b/author         : author [ String ]{1, *}
    b/title          : title  [ String ]

The type system can determine that b is always Book, therefore the type of b/author is author[ String ]{1, *}, and the type of b/title is title[ String ].

In general, the value of a for expression is a forest. If the body of the for expression itself yields a forest, then all of the forests are concatenated together. For instance, the expression:

    for b in bib0/book do
      b/author

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

Here we have explained the typing of for expressions by example. In fact, the typing rules are rather subtle and will be explained in detail in [5 Type Rules].

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 do 
      where b/@year/data() <= 2000 do
        b
==> book [
     @year  [ 1999 ], 
     @isbn  [ "1-55860-622-X" ], 
     title  [ "Data on the Web" ], 
     author [ "Abiteboul" ], 
     author [ "Buneman" ], 
     author [ "Suciu" ]
    ] 
:   Book{0, *} 

In general, an expression of the form:

where e₁ do 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 forest 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 do
  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 do
      for a in distinct(b/author/data()) do
        where a = "Buneman" do
          b
==> book [
     @year  [ 1999 ], 
     @isbn  [ "1-55860-622-X" ], 
     title  [ "Data on the Web" ], 
     author [ "Abiteboul" ], 
     author [ "Buneman" ], 
     author [ "Suciu" ]
    ] 
:   Book{0, *}

In contrast, we can use the empty operator to find all books that have no author whose name is Buneman:

    for b in bib0/book do
      where empty(for a in b/author do
                    where a/data() = "Buneman" do
                      a) do
        b
==> book [
      @year  [ 2001 ], 
      @isbn  [ "1-XXXXX-YYY-Z" ], 
      title  [ "XML Query" ], 
      author [ "Fernandez" ], 
      author [ "Suciu" ]
    ]
:   Book{0, *}

The empty expression checks that its argument is the empty sequence ().

We can also use the empty operator to find all books where all the authors are Buneman, by checking that there are no authors that are not Buneman:

    for b in bib0/book do
      where empty(for a in b/author do
                    where a/data() <> "Buneman" do
                      a) do
        b
==> ()
:   Book{0, *}

There are no such books, so the result is the empty sequence. Appropriate use of empty (possibly combined with not) can express universally or existentially quantified expressions.

Here is a good place to introduce the let expression, which binds a local variable to a value. Introducing local variables may improve readability. For example, the following expression is exactly equivalent to the previous one.

    for b in bib0/book do
      let nonbunemans = (for a in b/author do
                           where a/data() <> "Buneman" do
                             a) do
        where empty(nonbunemans) do
          b

Local variables can also be used to avoid repetition when the same subexpression appears more than once in a query.

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  =
      reviews [
        book [ 
          title  [ String ], 
          review [ String ]
        ]{0, *}
      ]
    let review0 : Reviews =
      reviews [
        book [
          title  [ "XML Query" ], 
          review [ "A darn fine book." ] 
        ], 
        book [
          title  [ "Data on the Web" ], 
          review [ "This is great!" ] 
        ]
      ] 

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 do
      for r in review0/book do
        where b/title/data() = r/title/data() do
          book [ b/title, b/author, r/review ]
==> 
    book [
      title  [ "Data on the Web" ], 
      author [ "Abiteboul" ], 
      author [ "Buneman" ], 
      author [ "Suciu" ]
      review [ "A darn fine book." ] 
    ], 
    book [
      title  [ "XML Query" ], 
      author [ "Fernandez" ], 
      author [ "Suciu" ]
      review [ "This is great!" ] 
    ]
:   book [
      title [ String ], 
      author [ String ] {1, *}, 
      review [ String ]
    ] {0, *}

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 the XML Query Algebra: changing the order of the first two for expressions would produce different output. In [B.2 Issues list], we discuss extending the algebra to support unordered forests, which would permit commutable joins.

2.8 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(bib0/book/author/data()) do
      biblio [
        author[a], 
        for b in bib0/book do
          for a2 in b/author/data() do
            where a = a2 do
              b/title
      ]
==> biblio [
      author [ "Abiteboul" ], 
      title  [ "Data on the Web" ]
    ], 
    biblio [
      author [ "Buneman" ], 
      title  [ "Data on the Web" ]
    ], 
    biblio [
      author [ "Suciu" ], 
      title  [ "Data on the Web" ], 
      title  [ "XML Query" ]
    ], 
    biblio [
      author [ "Fernandez" ], 
      title  [ "XML Query" ]
    ]
:   biblio [
      author [ String ], 
      title  [ String ] {0, *}
    ] {0, *}

Readers may recognize this expression as a self-join of books on authors. The expression distinct(bib0/book/author) produces a forest of author elements with no duplicates. The outer for expression binds a to each author element, and the inner for expression selects the title of each book that has some author equal to a.

Here distinct is an example of a built-in function. It takes a forest of elements and removes duplicates by content; the order of the resulting forest is not defined.

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.9 Querying order

Often it is useful to query the order of elements in a forest. There are two kinds of order among elements. Document or global order refers to the total order among all elements in a document and corresponds to their sequential appearance. Local order refers to the order among sibling elements in a forest. Currently, the algebra supports querying of local order, but not global order. We discuss global order in [B.2 Issues list].

The index function pairs an integer index with each element in a forest:

    index(book0/author)
==> pair [ fst [ 1 ], snd [ author [ "Abiteboul" ] ] ], 
    pair [ fst [ 2 ], snd [ author [ "Buneman" ] ] ], 
    pair [ fst [ 3 ], snd [ author [ "Suciu" ] ] ]
:   pair [ fst [ Integer ], snd [ author [ String ] ] ] {1, *} 

Note that the result type guarantees that at least one pair exists in the result, because (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) do
      where (p/fst/data() <= 2) do
        p/snd/author
==> author [ "Abiteboul" ], 
    author [ "Buneman" ]
:   author [ String ] {0, *}

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

Once again, 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 clause will always succeed, so the inner clause may produce zero results. (A sophisticated analysis might improve type precision, but is likely to require much work for little benefit.)

2.10 Sorting

To sort a forest, the algebra provides a sort expression, whose form is: sort Var in Exp₁ by Exp₂. The variable Var ranges over the items in the forest Exp₁ and sorts those items using the key value defined by Exp₂. For example, this expression sorts book elements in review0 by their titles. Note that the variable b appear in the key expression b/title.

    sort b in review0/book by b/title
==> book [ title  [ "Data on the Web" ], 
           review [ "This is great!" ] ], 
    book [ title  [ "XML Query" ], 
           review [ "This is pretty good too!" ] ]
:   book [ title [ String ], review [ String ] ] ] {0, *}

The sort operator 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 should extract the key value from each element.

2.11 Aggregation

We have already seen several several built-in functions: index, distinct, and sort. In addition to these functions, the algebra 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 do
      where count(b/author) > 2 do
        b
==> book [
      @year  [ 1999 ], 
      @isbn  [ "1-55860-622-X" ], 
      title  [ "Data on the Web" ], 
      author [ "Abiteboul" ], 
      author [ "Buneman" ], 
      author [ "Suciu" ]
    ]
:   Book{0, *}

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

2.12 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:

    let inventory = 
      inv [ 
        {http://www.BooksRUs.com/books.xsd}book [
          @{http://www.BooksRUs.com/books.xsd}year  [ 1999 ], 
          @{http://www.BooksRUs.com/books.xsd}isbn  [ "1-55860-622-X" ],
          {http://www.BooksRUs.com/books.xsd}title  [ "Data on the Web" ], 
          {http://www.BooksRUs.com/books.xsd}author [ "Abiteboul" ], 
          {http://www.BooksRUs.com/books.xsd}author [ "Buneman" ], 
          {http://www.BooksRUs.com/books.xsd}author [ "Suciu" ]
        ], 
        {http://www.cheapBooks.com/ourschema.xsd}book [
          @{http://www.cheapBooks.com/ourschema.xsd}year  [ 2001 ], 
          {http://www.cheapBooks.com/ourschema.xsd}title  [ "XML Query" ], 
          {http://www.cheapBooks.com/ourschema.xsd}author [ "Fernandez" ], 
          {http://www.cheapBooks.com/ourschema.xsd}author [ "Suciu" ]
          {http://www.cheapBooks.com/ourschema.xsd}isbn   [ "1-XXXXX-YYY-Z" ], 
        ]
       ] 
     ] : Inventory
    type Inventory = inv [ InvBook{0, *}]

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

    type BooksRUBook = 
      {http://www.BooksRUs.com/books.xsd}book [
        @{http://www.BooksRUs.com/books.xsd}year  [ Integer ] & 
        @{http://www.BooksRUs.com/books.xsd}isbn  [ String ],
        {http://www.BooksRUs.com/books.xsd}title  [ String ], 
        {http://www.BooksRUs.com/books.xsd}author [ String ]{1, *}
      ]
    type CheapBooksBook = 
      {http://www.cheapBooks.com/ourschema.xsd}book [
        @{http://www.cheapBooks.com/ourschema.xsd}year  [ Integer ],
        {http://www.cheapBooks.com/ourschema.xsd}title  [ String ], 
        {http://www.cheapBooks.com/ourschema.xsd}author [ String ]{1, *},
        {http://www.cheapBooks.com/ourschema.xsd}isbn   [ 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/{http://www.BooksRUs.com/books.xsd}* 
==> {http://www.BooksRUs.com/books.xsd}book [
      {http://www.BooksRUs.com/books.xsd}title  [ "Data on the Web" ], 
      {http://www.BooksRUs.com/books.xsd}author [ "Abiteboul" ], 
      {http://www.BooksRUs.com/books.xsd}author [ "Buneman" ], 
      {http://www.BooksRUs.com/books.xsd}author [ "Suciu" ]
    ]
:   {http://www.BooksRUs.com/books.xsd}book [
      {http://www.BooksRUs.com/books.xsd}title  [ String ], 
      {http://www.BooksRUs.com/books.xsd}author [ String ] {0, *}, 
    ]

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

    inventory/{*}book/@{*}year
==> @{http://www.BooksRUs.com/books.xsd}year  [ 1999 ], 
    @{http://www.cheapBooks.com/ourschema.xsd}year  [ 2001 ], 
:   (@{http://www.BooksRUs.com/books.xsd}year  [ Integer ] | 
     @{http://www.cheapBooks.com/ourschema.xsd}year [ Integer ]){0,*} 

In general, the expression Exp/a is shorthand for Exp/{*}a, that is, the namespace wildcard can be omitted. Similarly, * is shorthand for {*}*.

2.13 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 do
      where empty(for a in b/author do
                    where a/data() = "Buneman" do
                      a) do
        b
==> book [
      @year  [ 2001 ], 
      @isbn  [ "1-XXXXX-YYY-Z" ], 
      title  [ "XML Query" ], 
      author [ "Fernandez" ], 
      author [ "Suciu" ]
    ]
:   Book{0, *}

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.

     fun notauthor (s : String; b : Book) : Boolean =
       empty(for a in b/author do
               where a/data() = s do
                 a)

The query can then be re-expressed as follows.

    for b in bib0/book do
      where notauthor("Buneman"; b) do
        b
==> book [
      @year  [ 2001 ], 
      @isbn  [ "1-XXXXX-YYY-Z" ], 
      title  [ "XML Query" ], 
      author [ "Fernandez" ], 
      author [ "Suciu" ]
    ]
:   Book{0, *}

We use semicolon rather than comma to separate function arguments, since comma is used to concatenate forests.

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 the algebra extensible. We have seen examples of built-in functions (sort and distinct) and examples of user-defined functions (notauthor). In addition to built-in and user-defined functions, the algebra could support externally defined functions, i.e., functions that are not defined in the algebra itself, but in some external language. This would make special-purpose implementations of, for example, full-text search functions available in the algebra. We discuss support for externally defined functions in [B.2 Issues list].

2.14 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 the algebra, 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 = 
      basic [
        cost [ Integer ]
      ]
    type Composite = 
      composite [
        assembly_cost [ Integer ], 
        subparts [ Part{1, *} ]
      ]

And here is some sample data.

    let part0 : Part =
      composite [
        assembly_cost [ 12 ], 
        subparts [
          composite [
            assembly_cost [ 22 ], 
            subparts [
              basic [ cost [ 33 ] ]
            ]
          ], 
          basic [ cost [ 7 ] ]
        ]
      ]

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 =
      part [
        total_cost [ Integer ], 
        subparts [ Part2{0, *} ]
      ]

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

    fun convert(p : Part) : Part2 =
      match p 
        case b : Basic do
          part [
            total_cost [ b/cost/data() ], 
            subparts []
          ]
        case c : Composite do 
          let s = (for y in children(c/subparts) do 
                     convert(y)) do
            part [
              total_cost [
                q/assembly_cost/data() + 
                  sum(s/total_cost/data())
              ], 
              subparts[ s ]
            ]
        else error

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

One might wonder why b and c are required, since they have the same value as p. The reason why is that p, b, and c have different types.

    p : Part
    b : Basic
    c : Composite

The types of b and c are 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 ], 
      subparts [
        part [
          total_cost [ 55 ], 
          subparts [
            part [
              total_cost [ 33 ], 
              subparts []
            ]
          ]
        ], 
        part [
          total_cost [ 7 ], 
          subparts []
        ]
      ]
    ]

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

2.15 Functions for all well-formed documents

Recursive types allow us to define a type that matches any well-formed XML document. This type is called AnyTree :

    type AnyTree        = AnyScalar | AnyElement | AnyAttribute
    type AnySimpleType  = AnyScalar | AnyScalar{0,*}
    type AnyAttribute   = @*[ AnySimpleType ]
    type AnyElement     = *[ AnyComplexType ]
    type AnyComplexType = AnyTree{0, *}
    type AnyType        = AnySimpleType | AnyComplexType

AnyTree stands for any scalar, element, or attribute value. Here AnyScalar is a built-in scalar type. It stands for the most general scalar type, and all other scalar types (like Integer or String) are subtypes of it. AnySimpleType stands for the most general simple type, which is a scalar or a list of scalars. AnyAttribute stands for the most general attribute type. The asterisk (*) is used to indicate a wild-card type, i.e., a type whose name is not known statically. The type AnyAttribute may have any name, and its content must have type AnySimpleType, i.e., it may contain atomic values, but no elements. The AnyElement stands for the most general element type, which may have any name, and its content must be a complex type, which is a repetition of zero or more AnyTrees. Finally, an AnyTree is either an AnySimpleType or an AnyComplexType. In other words, any element, attribute, or atomic value has type AnyType.

The use of * is a significant extension to XML Schema, because XML Schema has no type corresponding to *[t], where t is some type other than AnyComplexType. It is not clear that this extension is necessary, since the more restrictive expressiveness of XML Schema wildcards may be adequate.

In particular, our earlier data also has type AnyTree.

    book0 : AnyTree
==> book [
      @year  [ 1999 ], 
      @isbn  [ "1-55860-622-X" ], 
      title  [ "Data on the Web" ], 
      author [ "Abiteboul" ], 
      author [ "Buneman" ], 
      author [ "Suciu" ]
    ]
:   AnyTree

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 =
      ( AnyScalar
      | b [ HTML_body ]
      | ul [ (li [ HTML_body ]){0, *} ]
      ) {0, *}

An HTML body consists of a sequence of zero or more items, each of which is either a scalar, 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.

    fun html_of_xml( x : AnyTree ) : Html_Body =
      match x 
        case s : AnyScalar do s
        case v1 : AnyAttribute do 
          b [ name(v1) ], 
          ul [ for y in children(v1) do li [ html_of_xml(y) ] ],
        case v2 : AnyElement do 
          b [ name(v2) ], 
          ul [ for y in attributes(v2) do li [ html_of_xml(y) ], 
          ul [ for y in children(v2) do li [ html_of_xml(y) ] ]
        else error

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

The second branch checks whether the value of x is a subtype of AnyAttribute. As before, v1 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" ], 
    ul [
      li [ b [ "year" ],   ul [ li [ 1999 ] ] ], 
      li [ b [ "isbn" ],   ul [ li [ "1-55860-622-X" ] ] ],  
      li [ b [ "title" ],  ul [ li [ "Data on the Web" ] ] ], 
      li [ b [ "author" ], ul [ li [ "Abiteboul" ] ] ], 
      li [ b [ "author" ], ul [ li [ "Buneman" ] ] ], 
      li [ b [ "author" ], ul [ li [ "Suciu" ] ] ]
    ]
:   HTML_Body

2.16 Top-level queries

A query consists of a sequence of top-level expressions, or query items, where each query item is either a type declaration, a function declaration, a global variable declaration, or a query expression. The order of query items is immaterial; all type, function, and global variable declarations may be mutually recursive.

Each query expression is evaluated in the environment specified by all of the declarations. (Typically, all of the declarations will precede all of the query expressions, but this is not required.) We have already seen examples of type, function, and global variable declarations. An example of a query expression is:

    query html_of_xml(book0)

To transform any expression into a top-level query, we simply precede the expression by the query keyword.

3 Algebra Components

In this section, we summarize the algebra and present the grammars for types and expressions. We start by defining the non-terminal and terminal symbols that appear in the type and expression grammars.

3.1 Expanded names

A Namespace is a URI, and a LocalName is an NCName, as in the Namespace recommendation [XML Names]. We let Namespace range over namespaces and the null value, which represents the absence of a namespace, and LocalName range over NCNames. The symbol Name ranges over expanded names. An expanded name is either a local name for which the namespace is absent or namespace, local name pairs.

Ed. Note: MF (Oct-13-2000): We need to add the data model accessors that extract the namespace and the local name from an expanded name.

3.2 Wildcards

A wildcard denotes a set of names. A wildcard item is of the form {*}* denoting any name in any namespace, {Namespace}* denoting any name in namespace Namespace, {*}LocalName denoting the local name LocalName in any namespace, or {Namespace}LocalName denoting just the name with namespace Namespace and local name LocalName. A wildcard consists of wildcard items, union of wildcards, or difference of wildcards. We let WItem range over wildcard items, and Wild range over wildcard expressions.

For example, the wildcard {*}*!{http://www.foo.org/baz}*!{http://www.xsd.com/xsi}String denotes any name in any namespace except for names in namespace http://www.foo.org/baz and for local name String in namespace http://www.xsd.com/xsi.

Wildcards denote sets of expanded names, so we can define a containment relation, <:_wild that relate sets of wildcards. The inequalities that hold for this relation include:

The last inequality holds by transitivity. Note, however, that {*}LocalName <:_wild {Namespace}* does not necessarily hold.

3.3 Atomic types

The Algebra takes as given the atomic datatypes from XML Schema Part 2 [XSchema2]. We let p range over all atomic datatypes.

Typically, an atomic datatype is either a primitive datatype, or is derived from another atomic datatype by specifying a set of facets. A type hierarchy is induced between scalar types by containment of facets. Note that lists of atomic datatypes are specified using repetition and unions are specified using alternation, as defined in [3.4 Types : abstract syntax]

The built-in atomic data type AnyScalar stands for the most general scalar type, and all other scalar types (like Integer or String) are subtypes of it.

3.4 Types : abstract syntax

[Figure 1]  contains the abstract syntax for the Algebra's type system. A type is closely related to a model group as defined in [MSL]. MSL uses standard regular expression notation for model groups and we do the same for algebra types. This type system captures the essence of [XSchema1] and is similar to the type system used in XDuce [HP2000].

---

type variable y     type t ::= y type variable     | () empty sequence     | Ø empty choice     | Wild wildcard type     | u unit type     | t1 , t2 sequence, t1 followed by t2     | t1 | t2 choice, t1 or t2     | t1 & t2 all, t1 and t2 in either order     | t {m, n} repetition of t between m and n times bound m, n ::= natural number or * unit type u ::= p atomic datatype     | @Wild[t] attribute with name in Wild and content in t     | Wild[t] element with name in Wild and content in t prime type q ::= u     | q | q

---

Figure 1: Abstract Syntax for Types

---

Ed. Note: MF (Nov-16-2000): Explain why prime type is here.

Ed. Note: MF (Nov-16-2000): Explain why Wild occurs in types.

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.

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 {m, n} is equivalent to the empty choice Ø if m > n or if m is *.

The algebra's external type system, that is, the type definitions associated with input and output documents, is XML Schema. The internal types are in some ways more expressive than XML Schema, for example, XML Schema has no type corresponding to {*}*[t] where t is some type other than AnyComplexType. In general, mapping XML Schema types into internal types will not lose information, however, mapping internal types into XML Schema may lose information.

3.5 Types : concrete syntax

It is useful to define a concrete syntax for the Algebra's types using syntactic categories that specify various subsets of types. Syntactic classes 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.

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.

A simple type is either an atomic type, a list of atomic types, or a choice of atomic types, which allows a choice of atomic lists.

An attribute group defines the syntactic form of attributes: their content may only be a simple type and they are combined only in all groups, not sequences.

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

The content type of an element is either 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 algebraic expression may be an attribute group, an element group, or a content type:

Ed. Note: MF (Nov-16-2000): This needs work.

3.6 Expressions

[Figure 2]  contains the concrete syntax for expressions. A few of these expressions can be rewritten as other expressions in a smaller core algebra; such reducible expressions are labeled with "*". We define the algebra's typing rules on the smaller core algebra. In [4.3 Laws], we give the laws that relate a reducible expression with its equivalent expression in the core algebra. Typing rules for the core algebra are defined in [5 Type Rules].

We have seen examples of most of the expressions, so we will only point out details here. We define a subset of expressions that correspond to data values. An expression is a data value if it consists only of scalar constant, element, sequence, and empty sequence expressions.

---

name Name function FuncName variable Var constant Const atomic-datatype constant binary operator BinaryOp ::= + | - | and | or     | = | != | < | <= | >= | > unary operator UnaryOp ::= + | - | not name expression NameExp ::= Name | {Exp}Exp computed name expression Exp ::= Const atomic constant     | NameExp name expression     | Var variable     | @Name[Exp] attribute     | Name[Exp] element     | @NameExp[Exp] computed attribute     | NameExp[Exp] computed element     | Exp, Exp sequence     | () empty sequence     | if Exp then Exp else Exp conditional     | let Var = Exp do Exp local binding     | FuncName (Exp ;...; Exp) function application     | Exp : Type explicit type     | error error     | Exp BinaryOp Exp binary operator     | UnaryOp Exp unary operator     | attributes (Exp) attributes     | children (Exp) children     | name (Exp) element name     | for Var in Exp do Exp iteration     | match Exp match       case Var : Type do Exp       ···       case Var : Type do Exp       else Exp     | Exp / @Wild attribute projection *     | Exp / Wild element projection *     | Exp / data() atomic projection *     | where Exp do Exp where conditional *     | empty (Exp) emptiness predicate *     | cast Exp : Type run-time type cast *     | let Var : Type = Exp do Exp local variable with type * query item Query ::= type TypeVar = Type type declaration     | fun FuncName (Var : Type ; ... ; Var : Type): Type =         Exp function declaration     | let Var : Type = Exp global variable declaration     | query Exp query expression

---

Figure 2: Algebra Expression Syntax

---

Ed. Note: MF (Oct-13-2000): We need to add the data model accessors that extract the namespace and the local name from an expanded name.

We have not defined the semantics of the binary operators in the algebra. It might be useful to define more than one type of equality over scalar and element values. We leave that to future work.

[Figure 3]  summarizes the built-in functions of the algebra.

---

avg, count, min, max, sum	Aggregation functions
index	Pairs each element of a forest with integer index.
sort	Sorts elements on key value bound by variable argument.
distinct	Removes duplicates from a forest.
namespace	Extracts URI namespace from a name value.
localname	Extracts NCName local name from a name value.

---

Figure 2: Built-In Functions

---

Ed. Note: MF (Nov-16-2000): We need a section here on operational semantics of expressions. The intent of the "Algebra by Example" section is to do this by example, but a formal operational semantics for each operator is necessary. See [Issue-0074:  Operational semantics for expressions].

4 Equivalences

4.1 Relating projection to iteration

The examples use the / operator liberally, but in fact we use / as a convenient abbreviation for expressions built from lower-level operators: for expressions, the children function, and match expressions.

For example, the expression:

    book0/author

is equivalent to the expression:

    for v in children(book0) do
      match v 
        case a : author[AnyComplexType] do a
        else ()

Here the children function returns a forest consisting of the children of the element book0, namely, a title element and three author elements (the order is preserved). The for expression binds the variable v successively to each of these elements. Then the match expression selects a branch based on the type of v. If it is an author element then the first branch is evaluated, otherwise the second branch. If the first branch is evaluated, it returns a. The variable a contains the same value as v, but the type of a is author[String], which is the intersection of the type of v and the type author[AnyComplexType]. If the second branch is evaluated, then the branch returns (), the empty sequence.

To compose several expressions using /, we again use for expressions. For example, the expression:

    bib0/book/author

is equivalent to the expression:

    for b in children(bib0) do
      match b
        case b : book[AnyComplexType] do
          for d in children(b) do
            match d
              case a : author[AnyComplexType] do a
              else ()
        else ()

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 returns all the author elements in b, and the resulting forests are concatenated together in order.

In general, an expression of the form e / a is converted to the form

    for v1 in e do
      for v2 in children(v1) do
        match v2
          case v3 : a[AnyComplexType] do v3
          else ()

where e is an expression, a is an element name, and v₁, v₂, and v₃ are fresh variables (ones that do not appear in the expression being converted).

According to this rule, the expression bib0/book translates to

    for v1 in bib0 do
      for v2 in children(v1) do
        match v2
          case v3 : book[AnyComplexType] do v3 
          else ()

In [4.3 Laws], we discuss laws which allow us to simplify this to the previous expression:

    for v2 in children(bib0) do
      match v2
        case v3 : book[AnyType] do v3 
        else ()

Similarly, the expression bib0/book/author translates to

    for v4 in (for v2 in children(bib0) do
                 match v2
                   case v3 : book[AnyType] do v3 
                   else ()) do
      for v5 in children(v4) do
        match v5
          case v6 : author[AnyType] do v6
          else ()

Again, the laws will allow us to simplify this to the previous expression

    for v2 in children(bib0) do
      match v2
        case v3 : book[AnyType] do
          for v5 in children(v3) do
            match v5
              case v6 : author[AnyType] do v6
              else ()
        else ()

These examples illustrate an important feature of the algebra: high-level operators may be defined in terms of low-level operators, and the low-level operators may be subject to algebraic laws that can be used to further simplify the expression.

4.2 Reducible Expressions

[Figure 4]  contains the laws that relate the reducible expressions (i.e., those labeled with "*" in [Figure 2]) to equivalent expressions. In these definitions, Exp₁{Exp₂/ Var} denotes the expression Exp₁ in which all occurrences of the variable Var are replaced by the expression Exp₂.

In Rule 1, the projection expression e / Wild is rewritten as a for expression, which binds v to each element in the forest e, and returns the children elements of v whose name is in Wild. Similarly, Rule 2 rewrites the attribute projection expression e / @Wild as a match embedded in a for expression.

Rule 3 rewrites the e / data() expression by iterating over items in e. The nested match expression returns e's children if e is AnySimpleType. Otherwise, it returns the empty sequence.

Rule 4 simply rewrites a where expression by an if - then - else expression.

Rule  5 rewrites empty(e) as a match expression that returns true if the type of e is the empty sequence.

Rule  6 rewrites cast e : t as a match expression that returns the value of e with type t, if it has that type at runtime, otherwise it raises an error.

Rule 7 rewrites the let expression with a type as a let expression without a type by moving the type constraint into the expression.

---

e / Wild Þ for v1 in e do   for v2 in children (v1) do       match v2 case v3 : Wild[AnyType] do v3 else () (1)   e / @Wild Þ for v1 in e do   for v2 in children (v1) do       match v2 case v3 : @Wild[AnyType] do v3 else () (2)   e / data() Þ for v in e do match children(v)     case v : AnySimpleType do v     else () (3)   where e1 do e2 Þ if e1 then e2 else () (4)   empty(e) Þ match e case v : () do true else false (5)   cast e : t Þ match e case v : t do v else error (6)   let v : Type = e1 do e2 Þ let v = (e1: Type) do e2 (7)

---

Figure 4: Definitions

---

4.3 Laws

In this section, we describe some laws that hold for the algebra. These laws are important for defining rules that simplify algebraic expressions, such as eliminating unnecessary for or match expressions.

The iteration construct of the algebra is closely related to an important mathematical object called a monad. A monad, among other things, generalizes set, bag, and list types. In functional languages, the comprehension construct is used to express iteration over set, bag, and list types. A comprehension corresponds directly to a monad [Wad92], [Wad93], [Wad95].

The correspondence between the algebra's iteration construct and a monad is close, but not exact. Each monad is based on a unary type constructor, such as Set{t} or List{t}, representing a homogenous set or list where all elements are of type t. In the algebra, we have more complex and heterogenous types, such as a forest consisting of a title, a year, and a sequence of one or more authors. Also, one important component of a monad is the unit operator, which converts an element to a set or list. If x has type t, then set{x} is a unit set of type Set{t} or [x] is a unit list of type List{t}. In the algebra, we simply write, say, author["Buneman"], which stands for both a tree and for the unit forest containing that tree.

Monads satisfy three laws, and three corresponding laws are satisfied by the the Algebra's for expression.

First, iteration over a unit forest can be replaced by substition. This is called the left unit law.

for v in e1 do e2 = e2{v := e1}

provided that e₁ is a unit type (e.g., is an element or a scalar constant). We write e₂{v := e₁} to denote the result of taking expression e₂ and replacing occurrences of the variable v by the expression e₁. For example,

for v in author["Buneman"] do auth[v/data()] = auth["Buneman"]

The iteration over a forest of one item can always be eliminated using variable substitution.

Second, an iteration that returns the iteration variable is equivalent to the identity. This is called the right unit law.

for v in e do v = e

For example

for v in book0 do v = book0

An important feature of the type system described here is that the left side of the above equation always has the same type as the right side.

Third, there are two ways of writing an iteration over an iteration, both of which are equivalent. This is called the associative law.

for v2 in (for v1 in e1 do e2) do e3
= for v1 in e1 do (for v2 in e2 do e3)

For example, a projection over a forest includes an implicit iteration, so e / a = for v in e do v / a. Say we define a forest of bibliographies, bib1 = bib0, bib0. Then bib1/book/author is equivalent to the first expression below, which in turn is equivalent to the second.

for b in (for a in bib1 do a/book) do b/author
= for a in bib1 do (for b in a/book do b/author)

With nested relational algebra, the monad laws play a key role in optimizing queries. Similarly, the monad laws can also be exploited for optimization in this context.

For example, if b is a book, the following finds all authors of the book that are not Buneman:

  for a in b do
    where a/data() != Buneman do
      a

If l is a list of authors, the following renames all author elements to auth elements:

  for a' in l do
    auth[ a'/data() ]

Combining these, we select all authors that are not Buneman, and rename the elements:

  for a' in (for a in b do
    	       where a/data() != Buneman do
    		 a) do
    auth[ a'/data() ]

Applying the associative law for a monad, we get:

  for a in b do
    for a' in (where a/data() != Buneman do a) do
      auth[ a'/data() ]

Expanding the where clause to a conditional, we get:

  for a in b do
    for a' in (if a/data() != Buneman then a else ()) do
      auth[ a'/data() ]

Applying a standard law for distributing loops over conditionals gives:

  for a in b do
    if a/data() != Buneman then
      for a' in a do
        auth[ a'/data() ]
    else ()

Applying the left unit law for a monad, we get:

  for a in b do
    if a/data() != Buneman then
      auth[ a/data() ]
    else ()

And replacing the conditional by a where clause, we get:

  for a in b do
    where a/data() != Buneman do
      auth[ a/data() ]

Thus, simple manipulations, including the monad laws, fuse the two loops.

[4.1 Relating projection to iteration] ended with two examples of simplification. Returning to these, we can now see that the simplifications are achieved by application of the left unit and associative monad laws.

[Figure 5]  contains a dozen algebraic simplification laws. In a relational query engine, algebraic simplifications are often applied by a query optimizer before a physical execution plan is generated; algebraic simplification can often reduce the size of the intermediate results computed by a query evaluator. The purpose of our laws is similar -- they eliminate unnecessary for or match expressions, or they enable other optimizations by reordering or distributing computations. The set of laws given is suggestive, rather than complete.

---

E ::= if [] then e1 else e2   | let v = [] in e   | for v in [] do e   | match []   case v : t do e   ...   case v : t do e   | else e   for v in () do e Þ () (8)   for v in (e1, e2) do e3 Þ (for v in e1 do e3), (for v in e2 do e3) (9)   for v in e1 do e2 Þ e2{e1/ v},  if e1 : u (10)     for v in e do v Þ e (11)   E[ if e1 then e2 else e3] Þ if e1 then E[e2] else E[e3] (12)   E[ let v = e1 do e2] Þ let v = e1 do e[e2] (13)   E[ for v in e1 do e2] Þ for v in e1 do E[e2] (14)   E[ match e1 case v : t do e2 casev : t do en-1 ... else en ] Þ match e1 case v : t do E[ e2 ] ... case v : t do E[ en-1 ] else E[en ] (15)

---

Figure 5: Optimization Laws

---

Rules 8, 9, and 10 simplify iterations. Rule 8 rewrites an iteration over the empty sequence as the empty sequence. Rule 9 distributes iteration through sequence: iterating over the sequence (e₁, e₂) is equivalent to the sequence of two iterations, one over e₁ and one over e₂. Rule 10 eliminates an iteration over a single element or scalar. If e₁ is a unit type, then e₁ can be substituted for occurrences of v in e₂.

Ed. Note: MF (Oct-18-2000) The rules for eliminating trivial match expressions need to be written. They are more complex than those for the old case expressions.

Rule 11 eliminates an iteration when the result expression is simply the iteration variable v.

Rules 12--15 are used to commute expressions. Each rule actually abbreviates a number of other rules, since the context variable e stands for a number of different expressions. The notation e [e] stands for one of the six expressions given with expression e replacing the hole [] that appears in each of the alternatives. For instance, one of the expansions of Rule 14 is the following, when e is taken to be for v in [] do e :