Web and Semantic Web Query Languages: A Survey

3.1.7 The Query Language XQuery

An activity towards specifying an XML query language, now XQuery, has been launched by W3C shortly before the publication of the final XPath 1.0 and XSLT 1.0 recommendations.

Requirements and use cases have been given in [76, 77, 192]. Proposals, e.g., XQL and Quilt, have been made that have influenced XQuery [42]:

• XQL [244, 246] has influenced XPath. XQL does not have the full range of XPath axes. XQL has existential and universal quantifiers and set operations that are under reconsideration for XPath 2.0.
• Quilt [79] is very close to the current version of XQuery, mainly lacking its extensive type system. Quilt can be considered the predecessor of XQuery.

XQuery's developement is not completed. It represents the state-of-the-art of navigational XML query languages.

XQuery Principles: XQuery is an extension of XPath 2.0 adding:

• Sequences. Where in XPath 1.0 the results of path expressions are node sets, XQuery and XPath 2.0 use sequences. In contrast to XPath 1.0, sequences cannot only be composed of nodes but also atomic values.
• Strong typing. Like XPath 2.0, XQuery is a strongly typed language supporting most of the (simple and complex) data types of XML Schema, cf. [104]. Furthermore, many XQuery implementations provide (as an optional feature) static type checking.
• Construction, Grouping, and Ordering. Where XPath is limited to selecting parts of the input data, XQuery provides ample support for constructing new data. Constructors for all node types as well as the simple data types from XML Schema are provided. New elements can be created either by direct element constructors (that look just like XML elements) or computed element constructors (allowing the name of a newly constructed element to be the result of a part of the query), cf. Query 1 and 3 below.
• Variables. Like XPath 2.0, XQuery has variables defined in so-called FLWOR expressions.
  A FLWOR expression usually consists in one or more for clauses, an optional where clause, an optional order by, and a return clause.
  The for clause iterates over the items in the sequence returned by the path expression in its in part:

  for $book in //book

  iterates over all books selected by the path expression //book.
  The where clause specifies conditions on the selected data items.
  The order by clause allows the items to be processed in a certain order.
  The return clause specifies the result of the entire FLWOR expression (often using constructors as shown above).
  Additionally, FLWOR expressions may contain, after the for clauses, let clauses that also bind variables but without iterating over the individual data items in the sequence bound to the variable.
  FLWOR expressions resemble very much XSLT's explicit iteration, selection, and assignment constructs.
• User-defined functions. XQuery allows to define new, possibly recursive, functions.
• Unordered sequences. XQuery provides the unordered keyword indicating that the order of elements in sequences that are constructed or returned as result of XQuery expressions is not relevant. E.g.,

  unordered{for $book in //book return $book/name} 

  indicates that the nodes selected by //book may be processed in any order in the for clause and the order of the resulting name nodes also can be arbitrary (i.e. implementation dependent). Within unordered query parts, the result of expressions querying the order of elements in sequences such as fn:position or fn:last is non-deterministic.
• Universal and existential quantification. Both XPath 2.0 and XQuery 1.0 provide some and all for expressing existentially or universally quantified conditions (cf. Query 9)
• Schema validation. XQuery implementations may provide support for schema validation, both of input and constructed data, using the validate expression.
• Full host language. XQuery completes XPath with defining contexts for path expressions, e.g., declaring namespace prefixes and default namespace, importing function libraries and modules (optional), and (optionally) providing flexible means for serialization (shared with XSLT 2.0) [168].

Not all of XPath's axes are mandatory in XQuery implementations: ancestor, ancestor-or-self, following, following-sibling, preceding, and preceding-sibling do not have to be supported. This is no restriction to XQuery's expressiveness, as expressions using reverse axes can be rewritten [225], and the "horizontal axes", e.g., following and following-sibling, can be replaced by FLWOR expressions using the << and >> operators that compare two nodes with respect to their position in a sequence.

Sample Queries: All nine sample queries can be expressed in XQuery. Query 2 is omitted because it can be expressed as a simplification of of Query 1. Query 5 can be expressed in XPath. Query 8 and 9 are similar. Sincve Query 9 in XQuery exhibits an interesting anomaly, it is given below and Query 8 is not given.

Query 1 ("Select all Essays together with their authors, i.e. author items and corresponding names.") can be expressed in XQuery as follows (interpreting the phrase an essay as a book with type attribute equal to the id of the category Essay or one of its sub-categories represented as descendants in the XML structure):

<results> {
  let $doc := doc("http://example.org/books")/bookdata
  let $sub-of-essay := 
        $doc//category[@id="Essay"]/descendant-or-self::category
  for $book in $doc//book 
  where $book/@type = $sub-of-essay/@id
  return
    <result>
      { $book }
      { $book/author }
      { $book/author/name }
   </result> }
</results>  

Note the use of the let clause in line 2: the sequence of all sub-categories of the category with id Essay including that category itself (we use the reflexive transitive axis descendant-or-self) is bound to the variable. However, in contrast to a for expression, this sequence is not iterated over. Instead of the where clause in line 4 a predicate could be added to the path expression in line 3 resulting in the expression $doc//book[@type = $sub-of-essay/@id].

Query 3 ("Select all data items except ontology information and translators.") requires structural recursion while constructing new elements that are identical to the ones encountered, except omitting translator and category nodes. The following implementation shows the use of a user-defined, recursive function that copies the tree rooted at its first parameter $e, except all nodes in the sequence given as second parameter.

declare function 
  local:tree-except($e as element(), 
                    $exceptions as node()*) as element()*
{
    element {fn:node-name($e)} {
      $e/@* except $exceptions, (: copy the attributes :)
      for $child in $element/node() except $exceptions
      return
        if $child instance of element() 
          (: for elements process them recursively :) 
          local:tree-except($section) 
        else (: others (text, comments, etc. copy  :)
          $child
    }                 
};

document {
     let $doc :=  doc("http://example.org/books")/bookdata
     let $exceptions := $doc//translator union $doc//category
     local:tree-except($doc, $exceptions)
   }

Note the typing of the parameters: the first parameter is a single element, the second, a sequence of nodes and the function returns a sequence of elements. In the main part of the query, the document constructor is used to indicate that its content is to be the document element of the constructed tree.

Query 4 ("Invert the relation author (from a book to an author) into a relation authored (from an author to a book).")

<bookdata> {
  let $a := doc("http://example.org/books")//author
  for $name in distinct-values($a/name)
  return
    <person>
      <name> { $name } </name>
      <authored
      {
         for $b in doc("http://example.org/books")//book
         where some $ba in $b/author 
               satisfies $ba/name = $name
         return 
           <book> { $b/@*, $b/* except $b/author } </book>
      }
      </authored
    </person>
  }
</bookdata>

This implementation is in fact similar to the implementation of use case XMP-Q4 in [76]. It exhibits two noteworthy functionalities:

• The use of distinct-value in line 3 to avoid duplication in the result, if an author occurs several times in the document.
• The use of an existentially quantified condition in lines 10-11, to find books where some (i.e. at least one) of the authors have the same name as the currently considered author.

Using aggregation expressions (see lines 8 and 10), Query 6 ("Return each of the subclasses of 'Writing', together with the average number of authors per publication of that subclass.") can be expressed in XQuery as follows:

<results> {
  let $doc := doc("http://example.org/books")/bookdata
  for $category in $doc//category[@id="Essay"]//category 
  return 
    <category>
      { $category/@id }
      <average-number-of-authors>{ 
        fn:avg(for $book in $doc//book
               where @type = $category/@id
               return fn:count($book/author))
      }
      </average-number-of-authors>
    </category>
  }
</results>

Combining data can be expressed in a very compact manner in XQuery, as the following expression of Query 7 ("Combine the information about the book titled 'The Civil War' and authored by 'Julius Caesar' with the information about the book with identifier 'bellum_civile'.") shows:

<book>
  { for $book in doc("http://example.org/books")//book
    where title="Bellum Civile" and author/name="Julius Caesar"
    return ($book/@*, $book/*)
  }
  {
    for $book in doc("http://example.org/books")//book
    where @id="bellum_civile"
    return ($book/@*, $book/*)
  } 
</book>

Query 9 ("Return the co-author relationship between two persons that stand in author relationships with the same book.") can be expressed in XQuery as follows:

<results>
  { let $doc := doc("http://example.org/books")
    for $book in doc("http://example.org/books")//book
      for $author in $book/author
        for $co-author in $book/author
        where $author << $co-author
        return 
          <co-authors>
            <name> { $author/name } </name>
            <name> { $co-author/name } </name>
          </co-authors>
  }
</results>

This implementation does not treat the case where two authors co-authored multiple books. In this case, duplicates are created by the above solution. To avoid this the following refinement uses the before operator << in combination with a negated condition, for specifying that only such pairs of authors should be considered, where there is no book that occurs prior to the currently considered one and which is also co-authored by the current pair of authors:

<results>
  { let $doc := doc("http://example.org/books")
    for $book in doc("http://example.org/books")//book
      for $author in $book/author
        for $co-author in $book/author
        where $author << $co-author and not(
          some $pb in doc("http://example.org/books")//book 
          satisfies ($pb << $book and  
                     $pb//author/name = $author/name and
                     $pb//author/name = $co-author/name))
        return 
          <co-authors>
            <name> { $author/name } </name>
            <name> { $co-author/name } </name>
          </co-authors>
  }
</results>

It is intuitively clear that XQuery is Turing complete since it provides recursive functions and conditional expressions. A proof of the Turing-completeness of XQuery is given in [169].

fun f1(T1 ∪ T2)   = f1(T1) ∪ f1(T2)
  | f1({ L => T }) = if L = book 
                                then {result => book => T} 
                                else f1(T)
  | f1({})         = {}
  | f1(V)          = {}

select { results => { 
  select { result => { Book, 
    select { author => { 
               author => Author,
               authorName => Name 
             } }
    where { author => \Author } ← Book, 
          { name => \Name } ← Author
  where { book => \Book } ← Bib 
where bookdata => Bib ← DB

book => author

_*

[^book]**

traverse DB given X
  case translator => _ then X := {}
  case category => _   then X := {}
  case \L => _         then X := {l => X}

WHERE
   <bookdata>
     <book>
     </> ELEMENT_AS $b
   </>
CONSTRUCT 
   <results>
     <result>
       $b
       WHERE <author>
               <name> $n </>
             </> ELEMENT_AS $a 
       CONSTRUCT $a
                 $n
     </>
   </>

WHERE
  <book type=$Sub>  
  </> ELEMENT_AS $b,
  <category id='Novel'>  
    <category* id=$Sub>
    </>
  </>
CONSTRUCT $b

WHERE
  <bookdata>
    $B: <book>
          $A: <author>
                <name> $N </name>
              </>
         </>
  </> 
CONSTRUCT 
  <results>
    <result>
      $B
      <book-author>
        $A
        <name> $N </name>
      </> {$A,$N}
    </> {$B}
  </>

WHERE
  <bookdata>
    $B: <book>
          $A: <author>
                <name> $N </name>
              </>
        </>
  </> 
CONSTRUCT 
  <results>
    [<result>
      $B
       [<book-author>
         $A
         <name> $N </name>
       </book-author>]
    </>]
  </>

GOAL
results [ 
  all result [
    var Book, 
    all var Author, 
    all var AuthorName
  ]
]
FROM
bookdata {{
  var Book → book {{
    var Author → author {{ 
      name [ var AuthorName ] }} 
    }} 
  }}
END

GOAL
   var Result
FROM
transform [ bookdata {{ }}, result [ var Result ] ]
END

CONSTRUCT
transform [ var Element, result [ ] ]
FROM
desc var Element → /translator|category/
END

CONSTRUCT
transform [ var Element, result [ var Label [ all var Child ] ] ]
FROM
and {
  desc var Element → var Label [[ var Child ]]
  where { 
         and { var Label != "translator", var Label != "category }
        }, 
  transform [ var Child, result [ var ChildTransformed ] ]
}
END

GOAL
bookdata [
  all person [
    name [ var Name ],
    authored [
      all book [
        all var NonAuthorChildren
      ] group by { var Book } 
    ]
  ]
]
FROM
bookdata {{
  desc var Book → book [[
    author {{ name [ var Name ] }}, 
    var NonAuthorChildren → !/author/ {{ }}
  ]]
}}
END

GOAL
results [
  all category [
    attributes [ id [ var ID ] ], 
    average-number-of-authors [
      div( count( all var Author ), count( all var Book ) )
    ]
  ]  
]
FROM
bookdata {{
  desc category {{ attributes {{ id [ var ID ] }} }},
  desc var Book → book {{ 
    attributes {{ type [ var ID ] }},
    desc var Author → author {{ }} 
  }}
}}
END

GOAL
results [
  all co-authors [
    name [ var Author ], 
    name [ var CoAuthor ]
  ]
]
FROM
bookdata {{
  desc book {{
    author {{ name {{ var Author }} }},
    author {{ name {{ var CoAuthor }} }}
}}
END

SELECT ?essay, ?author, ?authorName
FROM   http://example.org/books
WHERE  (?essay, <rdf:type>, <books:Essay>),
       (?essay, <books:author>, ?author),
       (?author, <books:name>, ?authorName)
USING  books FOR http://example.org/books#,
       rdf FOR http://www.w3.org/1999/02/22-rdf-syntax-ns#

SELECT ?property, ?propertyValue
FROM   http://example.org/books
WHERE  (?essay, <books:book-title>, "Bellum Civile")
       (?essay, ?property, ?propertyValue),
USING  books FOR http://example.org/books#

SELECT ?property, ?propertyValue
FROM   http://example.org/books
WHERE  (?essay, <books:book-title>, "Bellum Civile")
       (?essay, ?property, ?propertyValue),
USING  books FOR http://example.org/books#

SELECT ?person
FROM   http://example.org/books
WHERE  (?book, <books:author>, ?person)
       (?book, <books:title>, ?title)
AND    ?title = 'Bellum Civile'

PREFIX   books: http://example.org/books#
PREFIX   rdf: http://www.w3.org/1999/02/22-rdf-syntax-ns#
SELECT   ?essay, ?author, ?authorName, ?translator
FROM     http://example.org/books
WHERE    (?essay  books:author     ?author),
         (?author books:authorName ?authorName)
OPTIONAL (?essay  books:translator ?translator)

PREFIX   books: http://example.org/books#
CONSTRUCT (?y books:authored ?x)
FROM      http://example.org/books
WHERE     (?x books:author ?y)

PREFIX    books: http://example.org/books#
CONSTRUCT (?x books:co-author ?y)
FROM      http://example.org/books
WHERE     (?book books:author ?x)
          (?book books:author ?y)
AND       (?x neq ?y)

SELECT ?books
WHERE  ?graph ( ?books books:rating ?rating )
      (?graph   swp:assertedBy ?warrant)
       (?warrant swp:authority <http://people.net/cicero>)
USING  books FOR http://example.org/books#,
       swp   FOR <http://www.w3.org/2004/03/trix/swp-1/>

subClassOf(books:Writing)

topclass(books:Historical Essay)

nca(books:Historical Essay, books:Historical Novel)