Quilt: an XML query language

Introduction

A first look at Quilt

<?xml version="1.0"?>
<!DOCTYPE bib SYSTEM "books.bibitemd">
<bib>
<book>
<title>Harold and the Purple Crayon</title>
<author>
<lastname>Johnson</last>
<firstname>Crockett</first>
</author>
<pubinfo>
<publisher>Harper and Row</publisher>
<price>$4.76</price>
<year>1955</year>
</pubinfo>
</book>
<book>
<title>Harold's Fairy Tale</title>
<author>
<lastname>Johnson</last>
<firstname>Crockett</first>
</author>
<pubinfo>
<publisher>Harper and Row</publisher>
<price>$4.76</price>
<year>1956</year>
</pubinfo>
</book>
<book>
<title>Rise Up Singing</title>
<author>
<lastname>Blood</last>
<firstname>Peter</first>
</author>
<author>
<lastname>Patterson</last>
<firstname>Annie</first>
</author>
<pubinfo>
<publisher>Sing Out Corporation</publisher>
<price>$15.45</price>
<year>1988</year>
</pubinfo>
</book>
</bib>

FOR    $b IN document("http://www.biblio.com/books.xml")//book,
$a IN $b/author
WHERE  $a/firstname = "Crockett" AND  $a/lastname = "Johnson"
RETURN $b

<Result>
(
FOR    $b IN document("http://www.biblio.com/books.xml")//book,
$a IN $b/author
WHERE  $a/firstname = "Crockett"
AND  $a/lastname = "Johnson"
RETURN $b
)
</Result>

<Result>
(
FOR $a IN DISTINCT document("http://www.biblio.com/books.xml")//author
RETURN
<BooksByAuthor>
<Author>
$a/lastname/text()
</Author>
(
FOR $b IN document("http://www.biblio.com/books.xml")//book[author=$a]
RETURN $b/title SORTBY(title)
)
</BooksByAuthor> SORTBY(Author)
)
</Result>

<Result>
<BooksByAuthor>
<Author>Blood</Author>
<title>Rise Up Singing</title>
</BooksByAuthor>
<BooksByAuthor>
<Author>Johnson</Author>
<title>Harold and the Purple Crayon</title>
<title>Harold's Fairy Tale</title>
</BooksByAuthor>
<BooksByAuthor>
<Author>Patterson</Author>
<title>Rise Up Singing</title>
</BooksByAuthor>
</Result>

The following points are worth noting about the above example:

1. This example illustrates how a query can be nested inside another query. The variable $a, defined in the outer query, ranges over the set of distinct authors in the input document. The variable $b, defined in the inner query, ranges over the individual books written by a given author.
   
2. The data contained in the "Author" elements of the output document is selected from the "lastname" elements of the input document. The contents of these elements are extracted using XPath expressions that use the text () function, and then enclosed in new tags in the RETURN clause.
   
3. The order of elements in the output document is controlled by SORTBY clauses in both the inner and outer queries.
   
4. The predicate [author = $a] involves a comparison of complex types. Quill compares elements that have substructure by normalizing whitespace and testing for the same content and structure, in the same sequence. One concrete way to do this is by serializing content and markup. For example, the normalized string value of an element might be formed by serializing the markup, removing leading and trailing whitespace for each element, and removing whitespace between tags. Here is a sample <author> element, normalized using this scheme: <last>Johnson</last><first>Crockett</first>
   Once a complex element has been converted to a normalized string form, it can be compared to the normalized string value of another complex element.
   

FOR    $b IN //book,
$a IN $b/author
WHERE  $a/first = "Crockett"
AND  $a/last = "Johnson"
RETURN $b

The Quilt language

Syntax

1. The BEFORE and AFTER operators. "a BEFORE b" evaluates to the set of nodes in 'a' that occur before some node in 'b'. "a AFTER b" evaluates the set of nodes in 'a' that occur after some node in 'b'. In the section "Querying Structured Documents, we will see how these operators are used for expressing conditions based on sequence.
   
2. The INTERSECT operator. "a INTERSECT b" evaluates to the set of nodes in 'a' that are also found in 'b'. This is an enhancement to XPath, which contains an operator for set union but not for intersection.
   
3. The EXCEPT operator. "a EXCEPT b" evaluates to the set of nodes in 'a' that are not also found in 'b'.
   

FOR

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title> Books By Author </title>
</head>
<body>
<p>
The following table lists authors and books written
by each author.
</p>
<table wibibitemh="50%" border="1">
(
FOR $a IN DISTINCT //author ,
$b IN //book[author = $a]
RETURN
<tr>
<td>
$a/first/text(),
$a/last/text()
</td>,
<td>
$b/title/text()
</td>
</tr>
)
</table>
</body>
</html>

LET

LET $b := //book
RETURN
<avgprice> avg($b/price) </avgprice>

FOR $pub IN DISTINCT //publisher
LET $pri := document("http://www.biblio.com/books.xml")
//book/pubinfo[publisher=$pub]/price
RETURN
<pubinfo>
$pub ,
<avgprice> avg($pri) </avgprice>
</pubinfo>

WHERE

<orphan_books>
(
FOR $b IN //book
WHERE exists($b/title)
AND NOT exists($b/author)
RETURN $b/title
)
</orphan_books>

FOR $pub IN DISTINCT //publisher
LET $bk := //book[pubinfo/publisher=$pub]
WHERE count($bk) > 100
RETURN $pub

FOR $pub IN DISTINCT //publisher
LET $bk := //book[pubinfo/publisher=$pub AND pubinfo/year="1999"]
WHERE count($bk) > 100
RETURN $pub

RETURN

<result>
(
FOR $p IN DISTINCT //publisher
RETURN
<publisher>
<name>
$p/text()
</name> ,
<books>
(
FOR $t IN DISTINCT //book[pubinfo/publisher = $p]/title
RETURN $t SORTBY(.)
)
</books> ,
<authors>
(
FOR $a IN DISTINCT //book[pubinfo/publisher = $p]/author
RETURN $a SORTBY(lastname, firstname)
)
</authors>
</publisher> SORTBY(name)
)
</result>

Filtering documents

<Section><Title>Desserts</Title>
<Para>This section tells you all about yummy desserts.</Para>
<Section><Title>Cookies</Title>
<Para>Cookies are flat things that sometimes have chocolate chips.
<Figure image="cookie1"><Title>A Big Cookie</Title></Figure>
</Para>
</Section>
<Section><Title>Candy</Title>
<Para>Candy is dandy.</Para>
</Section>
<Section><Title>Pies and Tarts</Title>
<Para>Pies and tarts are even better.</Para>
<Figure image="applepie"><Title>An Apple Pie</Title></Figure>
<Figure image="peachpie"><Title>A Peach Pie</Title></Figure>
</Section>
<Section><Title>Cakes and Cupcakes</Title>
<Para>Cakes and Cupcakes are absolutely awesome.</Para>
<Section><Title>Cakes</Title>
<Figure image="choc_cake"><Title>A Chocolate Cake</Title></Figure>
</Section>
<Section><Title>Cupcakes</Title>
<Para>Cupcakes are not as big but just as good.</Para>
</Section>
</Section>
</Section>

<toc>
(
LET $s := document("cookbook.xml")
FILTER //Section | //Section/Title | //Section/Title/text()
RETURN $s
)
</toc>

<Section><Title>Desserts</Title>
<Section><Title>Cookies</Title>
</Section>
<Section><Title>Candy</Title>
</Section>
<Section><Title>Pies and Tarts</Title>
</Section>
<Section><Title>Cakes and Cupcakes</Title>
<Section><Title>Cakes</Title>
</Section>
<Section><Title>Cupcakes</Title>
</Section>
</Section>
</Section>

FUNCTION section_summary($s)
{
<Section>
$s/Title ,
(
LET $f := $s/Figure
RETURN <Figcount> count($f) </Figcount>
) ,
(
FOR $ss IN $s/Section
RETURN section_summary($ss)
)
}

<toc>
LET $stf := document("cookbook.xml")
FILTER //Section | //Title | //Figure
FOR $s IN $stf/Section
RETURN section_summary($s)
</toc>

<Section><Title>Desserts</Title>
<Figcount> 0 </Figcount>
<Section><Title>Cookies</Title>
<Figcount> 1 </Figcount>
</Section>
<Section><Title>Candy</Title>
<Figcount> 0 </Figcount>
</Section>
<Section><Title>Pies and Tarts</Title>
<Figcount> 2 </Figcount>
</Section>
<Section><Title>Cakes and Cupcakes</Title>
<Figcount> 0 </Figcount>
<Section><Title>Cakes</Title>
<Figcount> 1 </Figcount>
</Section>
<Section><Title>Cupcakes</Title>
<Figcount> 0 </Figcount>
</Section>
</Section>
</Section>

Querying relational data

<users>
<user_tuple>
<userid> 1005 </userid>
<name> Baker </name>
<rating> B </rating>
</user_tuple>
<user_tuple>
<userid> 1007 </userid>
<name> Carter </name>
<rating> A </rating>
</user_tuple>
</users>

<!DOCTYPE users [
<!ELEMENT users (user_tuple*)>
<!ELEMENT user_tuple (userid, name, rating)>
<!ELEMENT userid (#PCDATA)>
<!ELEMENT name (#PCDATA)>
<!ELEMENT rating (#PCDATA)>
]>

<!DOCTYPE items [
<!ELEMENT items (item_tuple*)>
<!ELEMENT item_tuple (itemno, description, offered_by, reserve_price)>
<!ELEMENT itemno (#PCDATA)>
<!ELEMENT description (#PCDATA)>
<!ELEMENT offered_by (#PCDATA)>
<!ELEMENT reserve_price (#PCDATA)>
]>

<!DOCTYPE bids [
<!ELEMENT bids (bid_tuple*)>
<!ELEMENT bid_tuple (userid, itemno, bid_amount, bid_date)>
<!ELEMENT userid (#PCDATA)>
<!ELEMENT itemno (#PCDATA)>
<!ELEMENT bid_amount (#PCDATA)>
<!ELEMENT bid_date (#PCDATA)>
]>

1. Q2 binds two variables. Variable $i ranges over all the distinct item numbers in the BIDS table. Variable $b represents the set of rows in the BIDS table that contain item numbers that match $i. The RETURN clause is executed once for each distinct item number.
   
2. The argument of the max function is $b/bid_amount. $b is bound to a set of bid_tuple elements, $b/bid_amount represents the set of bid_amount elements that are nested inside these bid_tuple elements, and max($b/bid_amount) returns the maximum of the values of the bid_amount elements in the set.
   
3. In Q2, the condition that appears in square brackets in the LET clause could not have been expressed in a WHERE-clause, since it is essential to the definition of the set to which $b is bound. Any search-conditions that apply to $b in a WHERE-clause would accept or reject the whole set represented by $b rather than individual elements of the set.
   

1. The results of the SQL query and the Quilt query are not exactly the same. Since SQL is a relational language, the result of an SQL query is always a table. In the SQL query result for Q5, each user's name is repeated in the query output for each item offered by that user. Quilt, on the other hand, takes advantage of the hierarchical nature of XML to avoid repeating user names. In the Quilt query result for Q5, each user name appears once, in an element with the tag USER, and all the items offered by a given user are nested inside the appropriate USER element.
   
2. In previous queries, when a SORTBY clause was used to specify the ordering of a set of elements in the query result, the argument of SORTBY was the name of the nested element to be used as the sort key. In the result of Q5, however, we wish the <offering> elements to be sorted by their own string values rather than by the value of a nested element. Therefore, we specify "SORTBY(.)", indicating that the sort key is the element itself.
   

Querying structured documents

<section><section.title>Procedure</section.title>
The patient was taken to the operating room where
she was placed in a supine position and
<Anesthesia>induced under general anesthesia.</Anesthesia>
<Prep>
<action>Foley catheter was placed to decompress the bladder</action>
and the abdomen was then prepped and draped in sterile fashion.
</Prep>
<Incision>
A curvilinear incision was made
<Geography>in the midline immediately infraumbilical</Geography>
and the subcutaneous tissue was divided
<Instrument>using electrocautery.</Instrument>
</Incision>
The fascia was identified and
<action>#2 0 Maxon stay sutures were placed
on each side of the midline.</action>
<Incision>
The fascia was divided using
<Instrument>electrocautery</Instrument>
and the peritoneum was entered.
</Incision>
<Observation>The small bowel was identified</Observation>
and
<action>
the
<Instrument>Hasson trocar</Instrument>
was placed under direct visualization.
</action>
<action>
The
<Instrument>trocar</Instrument>
was secured to the fascia using the stay sutures.
</action>
<!-- The section continues, but we excerpt it here... -->

Exploiting references in documents

//Figref/@target->

//Figref/@target->/Title

Conclusion