XML Query Algebra

Statically typed, functional language

• Query : Schema1 -> Schema2

  Query (Document1 : Schema1) => (Document2 : Schema2)

• Permits type-correct composition of queries (reuse)

Operators defined on data model

• Expression grammar : 20 productions

• 8 built-in functions

Basis of formal semantics for language

• Query translation & optimization

Type system

• Based on regular-tree languages

• Type grammar : 13 productions