# management of XML data with database techniques - Database system concepts

Unlike most of the technologies presented in the preceding chapters, the Extensible Markup Language (XML) was not originally conceived as a database technology. In fact, like the Hyper-Text Markup Language (HTML) on which the World Wide Web is based, XML has its roots in document management, and is derived from a language for structuring large documents known as the Standard Generalized Markup Language(SGML). However, unlike SGML and HTML, XML can represent database data, as well as many other kinds of structured data used in business applications. It is particularly useful as a data format when an application must communicate with another application, or integrate information from several other applications. When XML is used in these contexts, many database issues arise, including how to organize, manipulate,and query the XML data. In this chapter,we introduce XML and discuss both the management of XML data with database techniques and the exchange of data formatted as XML documents.

Background

To understand XML, it is important to understand its roots as a document markup language. The term markup refers to anything in a document that is not intended to be part of the printed output. For example, a writer creating text that will eventually be typeset in a magazine may want to make notes about how the typesetting should be done. It would be important to type these notes in a way so that they could be distinguished from the actual content, so that a note like “do not break this paragraph” does not end up printed in the magazine. In electronic document processing, a markup language is a formal description of what part of the document is content, what part is markup, and what the markup means.

Just as database systems evolved from physical file processing to provide a separate logical view, markup languages evolved from specifying instructions for how to print parts of the document to specify the function of the content. For instance, with functional markup, text representing section headings (for this section, the words “Background”) would be marked up as being a section heading, instead of being marked up as text to be printed in large size, bold font. Such functional markup allowed the document to be formatted differently in different situations. It also helps different parts of a large document, or different pages in a large Web site to be formatted in a uniform manner. Functional markup also helps automate extraction of key parts of documents.

For the family of markup languages that includes HTML, SGML, and XML the markup takes the form of tags enclosed in angle-brackets, <>. Tags are used in pairs, with <tag> and </tag> delimiting the beginning and the end of the portion of the document to which the tag refers. For example, the title of a document might be marked up as follows.

Unlike HTML, XML does not prescribe the set of tags allowed, and the set may be specialized as needed. This feature is the key to XML’s major role in data representation and exchange, whereas HTML is used primarily for document formatting. For example, in our running banking application, account and customer information can be represented as part of an XML document as in Figure . Observe the use of tags such as account and account-number. These tags provide context for each value and allow the semantics of the value to be identified.

Compared to storage of data in a database, the XML representation may be inefficient, since tag names are repeated throughout the document. However, in spite of this disadvantage, an XML representation has significant advantages when it is used to exchange data, for example, as part of a message:

• First, the presence of the tags makes the message self-documenting; that is, a schema need not be consulted to understand the meaning of the text. We can readily read the fragment above, for example.
• Second, the format of the document is not rigid. For example, if some sender adds additional information, such as a tag last-accessed noting the last date on which an account was accessed, the recipient of the XML data may simply ignore the tag. The ability to recognize and ignore unexpected tags allows the format of the data to evolve over time, without invalidating existing applications.
• Finally, since the XML format is widely accepted, a wide variety of tools are available to assist in its processing, including browser software and database tools.

Just as SQL is the dominant language for querying relational data, XML is becoming the dominant format for data exchange.

Figure XML representation of bank information.

Structure of XML Data

The fundamental construct in an XML document is the element. An element is simply a pair of matching start- and end-tags, and all the text that appears between them. XML documents must have a single root element that encompasses all other elements in the document. In the example in Figure the <bank> element forms the root element. Further, elements in an XML document must nest properly. For instance,

<account> . . . <balance> . . . </balance> . . . </account>

is properly nested, whereas

<account> . . . <balance> . . . </account> . . . </balance>

is not properly nested. While proper nesting is an intuitive property, we may define it more formally. Text is said to appear in the context of an element if it appears between the start-tag and end-tag of that element. Tags are properly nested if every start-tag has a unique matching end-tag that is in the context of the same parent element.

Note that text may be mixed with the subelements of an element, as in Figure As with several other features of XML, this freedom makes more sense in a documentprocessing context than in a data-processing context, and is not particularly useful for representing more structured data such as database content in XML.

The ability to nest elements within other elements provides an alternative way to represent information. Figure shows a representation of the bank information from Figure , but with account elements nested within customer elements. The nested representation makes it easy to find all accounts of a customer, although it would store account elements redundantly if they are owned by multiple customers. Nested representations are widely used in XML data interchange applications to avoid joins. For instance, a shipping applicationwould store the full address of sender and receiver redundantly on a shipping document associated with each shipment, whereas a normalized representation may require a join of shipping records with a company-address relation to get address information. In addition to elements, XML specifies the notion of an attribute. For instance, the type of an account can represented as an attribute, as in Figure The attributes of an element appear as name=value pairs before the closing “>” of a tag. Attributes are strings, and do not contain markup. Furthermore, attributes can appear only once in a given tag, unlike subelements, which may be repeated.

Figure Mixture of text with subelements.

Figure Nested XML representation of bank information.

Note that in a document construction context, the distinction between subelement and attribute is important an attribute is implicitly text that does not appear in the printed or displayed document. However, in database and data exchange applications of XML, this distinction is less relevant, and the choice of representing data as an attribute or a subelement is frequently arbitrary.

One final syntactic note is that an element of the form <element></element>, which contains no subelements or text, can be abbreviated as <element/>; abbreviated elements may, however, contain attributes.Since XML documents are designed to be exchanged between applications, a namespace mechanism has been introduced to allow organizations to specify globally unique names to be used as element tags in documents. The idea of a namespace is to prepend each tag or attribute with a universal resource identifier (for example, a Web address) Thus, for example, if First Bank wanted to ensure that XML documents

Figure Use of attributes.

it created would not duplicate tags used by any business partner’s XML documents, it can prepend a unique identifier with a colon to each tag name. The bank may use a Web URL such asa unique identifier. Using long unique identifiers in every tag would be rather inconvenient, so the namespace standard provides a way to define an abbreviation for identifiers.

In Figure , the root element (bank) has an attribute xmlns:FB, which declares that FB is defined as an abbreviation for the URL given above. The abbreviation can then be used in various element tags, as illustrated in the figure. A document can have more than one namespace, declared as part of the root element. Different elements can then be associated with different namespaces. A default namespace can be defined, by using the attribute xmlns instead of xmlns:FB in the root element. Elements without an explicit namespace prefix would then belong to the default namespace.Sometimes we need to store values containing tags without having the tags interpreted as XML tags. So that we can do so, XML allows this construct:

<![CDATA[<account> · · ·</account>]]>

Because it is enclosed within CDATA, the text <account> is treated as normal text data, not as a tag. The term CDATA stands for character data.

<bank xmlns:FB=“http://www.FirstBank.com”>
. . .
<FB:branch>
<FB:branchname> Downtown </FB:branchname>
<FB:branchcity> Brooklyn </FB:branchcity>
</FB:branch>
. . .
</bank>

Figure Unique tag names through the use of namespaces.

XML Document Schema

Databases have schemas, which are used to constrain what information can be stored in the database and to constrain the data types of the stored information. In contrast, by default, XML documents can be created without any associated schema: An element may then have any subelement or attribute. While such freedom may occasionally be acceptable given the self-describing nature of the data format, it is not generally useful when XML documents must be processesed automatically as part of an application, or even when large amounts of related data are to be formatted in XML.

Here, we describe the document-oriented schema mechanism included as part of the XML standard, the Document Type Definition, as well as the more recently defined XMLSchema.

Document Type Definition

The document type definition (DTD) is an optional part of an XML document. The main purpose of a DTD is much like that of a schema: to constrain and type the information present in the document. However, the DTD does not in fact constrain types in the sense of basic types like integer or string. Instead, it only constrains the appearance of subelements and attributes within an element. The DTD is primarily a list of rules for what pattern of subelements appear within an element. Figure shows a part of an example DTD for a bank information document; the XML document in Figure 10.1 conforms to this DTD.

Each declaration is in the form of a regular expression for the subelements of an element. Thus, in the DTD in Figure 10.6, a bank element consists of one or more account, customer, or depositor elements; the | operator specifies “or” while the + operator specifies “one or more.” Although not shown here, the * operator is used to specify “zero or more,” while the ? operator is used to specify an optional element (that is, “zero or one”).

Figure Example of a DTD

The account element is defined to contain subelements account-number, branchname and balance (in that order). Similarly, customer and depositor have the attributes in their schema defined as subelements. Finally, the elements account-number, branch-name, balance, customer-name, customer- street, and customer-city are all declared to be of type #PCDATA. The keyword #PCDATA indicates text data; it derives its name, historically, from “parsed character data.” Two other special type declarations are empty, which says that the element has no contents, and any, which says that there is no constraint on the subelements of theelement; that is, any elements, even those not mentioned in the DTD, can occur as subelements of the element. The absence of a declaration for an element is equivalent to explicitly declaring the type as any.

The allowable attributes for each element are also declared in the DTD. Unlike subelements, no order is imposed on attributes. Attributes may specified to be of type CDATA, ID, IDREF, or IDREFS; the type CDATA simply says that the attribute contains character data, while the other three are not so simple; they are explained in more detail shortly. For instance, the following line from a DTD specifies that elementaccount has an attribute of type acct-type, with default value checking.

Attributes must have a type declaration and a default declaration. The default declaration can consist of a default value for the attribute or #REQUIRED, meaning that a value must be specified for the attribute in each element, or #IMPLIED,meaning that no default value has been provided. If an attribute has a default value, for every element that does not specify a value for the attribute, the default value is filled in automatically when the XML document is read An attribute of type ID provides a unique identifier for the element; a value that occurs in an ID attribute of an element must not occur in any other element in the same document. At most one attribute of an element is permitted to be of type ID.

Figure DTD with ID and IDREF attribute types

An attribute of type IDREF is a reference to an element; the attribute must contain a value that appears in the ID attribute of some element in the document. The type IDREFS allows a list of references, separated by spaces. Figure shows an example DTD in which customer account relationships are represented by ID and IDREFS attributes, instead of depositor records. The account elements use account-number as their identifier attribute; to do so, account-number has been made an attribute of account instead of a subelement. The customer elements have a new identifier attribute called customer-id. Additionally, each customer element contains an attribute accounts, of type IDREFS, which is a list of identifiers of accounts that are owned by the customer. Each account element has an attribute owners, of type IDREFS, which is a list of owners of the account.

Note that we use a different set of accounts and customers from our earlier example, in order to illustrate the IDREFS feature better. The ID and IDREF attributes serve the same role as reference mechanisms in objectoriented and object-relational databases, permitting the construction of complex data relationships.

Figure XML data with ID and IDREF attributes.

Document type definitions are strongly connected to the document formatting heritage of XML. Because of this, they are unsuitable in many ways for serving as the type structure of XML for data processing applications. Nevertheless, a tremendous number of data exchange formats are being defined in terms of DTDs, since they were part of the original standard. Here are some of the limitations of DTDs as a schemamechanism.

• Individual text elements and attributes cannot be further typed. For instance, the element balance cannot be constrained to be a positive number. The lack of such constraints is problematic for data processing and exchange applications, which must then contain code to verify the types of elements and attributes.
• It is difficult to use the DTD mechanism to specify unordered sets of subelements. Order is seldom important for data exchange (unlike document layout, where it is crucial). While the combination of alternation (the | operation) and the * operation as in Figure permits the specification of unordered collections of tags, it is much more difficult to specify that each tag may only appear once.
• There is a lack of typing in IDs and IDREFs. Thus, there is no way to specify the type of element to which an IDREF or IDREFS attribute should refer. As a result, the DTD in Figure does not prevent the “owners” attribute of an account element from referring to other accounts, even though this makes no sense.

XML Schema

An effort to redress many of these DTD deficiencies resulted in a more sophisticated schema language, XMLSchema. We present here an example of XMLSchema, and list some areas in which it improves DTDs, without giving full details of XMLSchema’s syntax.

Figure shows how the DTD in Figure can be represented by XMLSchema. The first element is the root element bank, whose type is declared later. The example then defines the types of elements account, customer, and depositor. Observe the use of types xsd:string and xsd:decimal to constrain the types of data elements. Finally the example defines the type BankType as containing zero or more occurrences of each of account, customer and depositor. XMLSchema can define the minimum and maximum number of occurrences of subelements by using minOccurs and maxOccurs.

The default for both minimum and maximum occurrences is 1, so these have to be explicity specified to allow zero or more accounts, deposits, and customers. Among the benefits that XMLSchema offers over DTDs are these:

• It allows user-defined types to be created.
• It allows the text that appears in elements to be constrained to specific types, such as numeric types in specific formats or even more complicated types such as lists or union.

XMLSchema version of DTD

• It allows types to be restricted to create specialized types, for instance by specifying minimum and maximum values.
• It allows complex types to be extended by using a form of inheritance.
• It is a superset of DTDs.
• It allows uniqueness and foreign key constraints.
• It is integrated with namespaces to allow different parts of a document to conform to different schema.
• It is itself specified by XML syntax, as Figure shows.

However, the price paid for these features is that XMLSchema is significantly more complicated than DTDs.

Querying and Transformation

Given the increasing number of applications that use XML to exchange, mediate, and store data, tools for effective management of XML data are becoming increasingly important. In particular, tools for querying and transformation of XML data are essential to extract information from large bodies of XML data, and to convert data between different representations (schemas) in XML. Just as the output of a relational query is
a relation, the output of an XML query can be an XML document. As a result, querying and transformation can be combined into a single tool.

Several languages provide increasing degrees of querying and transformation capabilities:

• XPath is a language for path expressions, and is actually a building block for the remaining two query languages.
• XSLT was designed to be a transformation language, as part of the XSL style sheet system, which is used to control the formatting of XML data into HTML or other print or display languages. Although designed for formatting, XSLT can generate XML as output, and can express many interesting queries. Furthermore, it is currently the most widely available language for manipulating XML data.
• XQuery has been proposed as a standard for querying of XML data. XQuery combines features from many of the earlier proposals for querying XML, in particular the language Quilt.

Atree model of XML data is used in all these languages. An XML document is modeled as a tree, with nodes corresponding to elements and attributes. Element nodes can have children nodes, which can be subelements or attributes of the element. Correspondingly, each node (whether attribute or element), other than the root element, has a parent node, which is an element. The order of elements and attributes in theXML document is modeled by the ordering of children of nodes of the tree. The terms parent, child, ancestor, descendant, and siblings are interpreted in the tree model of XML data.

The text content of an element can be modeled as a text node child of the element. Elements containing text broken up by intervening subelements can have multiple text node children. For instance, an element containing “this is a <bold> wonderful</bold> book” would have a subelement child corresponding to the element bold and two text node children corresponding to “this is a” and “book”. Since such structuresare not commonly used in database data, we shall assume that elements do not contain both text and subelements.

XPath

XPath addresses parts of an XML document by means of path expressions. The language can be viewed as an extension of the simple path expressions in object-oriented and object-relational databases. A path expression in XPath is a sequence of location steps separated by “/” (instead of the “.” operator that separates steps in SQL:1999). The result of a path expression is a set of values. For instance, on the document in Figure , the XPath expression

would return the same names, but without the enclosing tags. Like a directory hierarchy, the initial ’/’ indicates the root of the document. (Note that this is an abstract root “above” <bank-2> that is the document tag.) Path expressions are evaluated from left to right. As a path expression is evaluated, the result of the path at any point consists of a set of nodes from the document.

When an element name, such as customer, appears before the next ’/’, it refers to all elements of the specified name that are children of elements in the current element set. Since multiple children can have the same name, the number of nodes in the node set can increase or decrease with each step. Attribute values may also be accessed, using the “@” symbol. For instance, /bank-2/account/@account-number returns a setof all values of account-number attributes of account elements. By default, IDREF links are not followed; we shall see how to deal with IDREFs later.

XPath supports a number of other features:

• Selection predicates may follow any step in a path, and are contained in square brackets. For example,
/bank-2/account[balance > 400]
returns account elements with a balance value greater than 400, while
/bank-2/account[balance > 400]/@account-number
returns the account numbers of those accounts.

We can test the existence of a subelement by listing it without any comparison operation; for instance, if we removed just “> 400” from the above, the expression would return account numbers of all accounts that have a balance subelement, regardless of its value.

• XPath provides several functions that can be used as part of predicates, including testing the position of the current node in the sibling order and counting the number of nodes matched. For example, the path expression /bank-2/account/[customer/count()> 2] returns accounts with more than 2 customers. Boolean connectives and and or can be used in predicates, while the function not(. . .) can be used for negation.
• The function id(“foo”) returns the node (if any) with an attribute of type ID and value “foo”. The function id can even be applied on sets of references, or even strings containing multiple references separated by blanks, such as IDREFS.
• For instance, the path
/bank-2/account/id(@owner) returns all customers referred to from the owners attribute of account elements.
• The | operator allows expression results to be unioned. For example, if the DTD of bank-2 also contained elements for loans, with attribute borrower of type IDREFS identifying loan borrower, the expression/bank-2/account/id(@owner) | /bank-2/loan/id(@borrower) gives customers with either accounts or loans. However, the | operator cannot be nested inside other operators.
• An XPath expression can skip multiple levels of nodes by using “//”. For instance, the expression /bank-2//name finds any name element anywhere under the /bank-2 element, regardless of the element in which it is contained. This example illustrates the ability to find required data without full knowledge of the schema.
• Each step in the path need not select from the children of the nodes in the current node set. In fact, this is just one of several directions along which a step in the path may proceed, such as parents, siblings, ancestors and descendants. We omit details, but note that “//”, described above, is a short form for specifying “all descendants,” while “..” specifies the parent.

XSLT

A style sheet is a representation of formatting options for a document, usually stored outside the document itself, so that formatting is separate from content. For example, a style sheet for HTML might specify the font to be used on all headers, and thus replace a large number of font declarations in the HTML page. The XML Stylesheet Language (XSL) was originally designed for generating HTML from XML, and is thusa logical extension of HTML style sheets. The language includes a general-purpose transformation mechanism, called XSL Transformations (XSLT), which can be used to transform one XML document into another XML document, or to other formats such as HTML.1 XSLT transformations are quite powerful, and in fact XSLT can even act as a query language.

Figure Using XSLT to wrap results in new XML elements.

XSLT transformations are expressed as a series of recursive rules, called templates. In their basic form, templates allow selection of nodes in an XML tree by an XPath expression. However, templates can also generate new XML content, so that selection and content generation can be mixed in natural and powerful ways. While XSLT can be used as a query language, its syntax and semantics are quite dissimilar from thoseof SQL.

A simple template for XSLT consists of a match part and a select part. Consider this XSLT code:

The xsl:template match statement contains an XPath expression that selects one or more nodes. The first template matches customer elements that occur as children of the bank-2 root element. The xsl:value-of statement enclosed in the match statement outputs values from the nodes in the result of the XPath expression. The first template outputs the value of the customer-name subelement; note that the value does notcontain the element tag.

Note that the second template matches all nodes. This is required because the default behavior of XSLT on subtrees of the input document that do not match any template is to copy the subtrees to the output document.XSLT copies any tag that is not in the xsl namespace unchanged to the output. Figure shows how to use this feature to make each customer name from our example appear as a subelement of a “<customer>” element, by placing the xsl:value-of statement between <customer> and </customer>.

Figure Applying rules recursively.

Structural recursion is a key part of XSLT. Recall that elements and subelements naturally form a tree structure. The idea of structural recursion is this: When a template matches an element in the tree structure, XSLT can use structural recursion to apply template rules recursively on subtrees, instead of just outputting a value. It applies rules recursively by the xsl:apply-templates directive, which appears inside other templates.

For example, the results of our previous query can be placed in a surrounding<customers> element by the addition of a rule using xsl:apply-templates, as in Figure The new rule matches the outer “bank” tag, and constructs a result document by applying all other templates to the subtrees appearing within the bank element, but wrapping the results in the given <customers> </customers> element.

Without recursion forced by the <xsl:apply-templates/> clause, the template would output <customers> </customers>, and then apply the other templates on the subelements. In fact, the structural recursion is critical to constructing well-formed XML documents, since XML documents must have a single top-level element containing all other elements in the document.

XSLT provides a feature called keys, which permit lookup of elements by using values of subelements or attributes; the goals are similar to that of the id() function in XPath, but permits attributes other than the ID attributes to be used. Keys are defined by an xsl:key directive, which has three parts, for example:

<xsl:key name=“acctno” match=“account” use=“account-number”/>

The name attribute is used to distinguish different keys. The match attribute specifies which nodes the key applies to. Finally, the use attribute specifies the expression to be used as the value of the key. Note that the expression need not be unique to an element; that is, more than one element may have the same expression value. In the example, the key named acctno specifies that the account-number subelement of account should be used as a key for that account.

Keys can be subsequently used in templates as part of any pattern through the key function. This function takes the name of the key and a value, and returns the set of nodes that match that value. Thus, the XML node for account “A-401” can be referenced as key(“acctno”, “A-401”).

Figure Joins in XSLT.

Keys can be used to implement some types of joins, as in Figure . The code in the figure can be applied to XML data in the format in Figure Here, the key function joins the depositor elements with matching customer and account elements. The result of the query consists of pairs of customer and account elements enclosed within cust-acct elements. XSLT allows nodes to be sorted. A simple example shows how xsl:sort would beused in our style sheet to return customer elements sorted by name:

Here, the xsl:apply-template has a select attribute, which constrains it to be applied only on customer subelements. The xsl:sort directive within the xsl:apply-template element causes nodes to be sorted before they are processed by the next set of templates. Options exist to allow sorting on multiple subelements/attributes, by numeric value, and in descending order.

XQuery

The World Wide Web Consortium (W3C) is developing XQuery, a query language for XML. Our discusssion here is based on a draft of the language standard, so the final standard may differ; however we expect the main features we cover here will not change substantially. The XQuery language derives from an XML query language called Quilt; most of the XQuery features we outline here are part of Quilt. Quilt itself includes features from earlier languages such as XPath, and two other XML query languages, XQL and XML-QL.

Unlike XSLT, XQuery does not represent queries in XML. Instead, they appearmore like SQL queries, and are organized into “FLWR” (pronounced “flower”) expressions comprising four sections: for, let, where, and return. The for section gives a series of variables that range over the results of XPath expressions. When more than one variable is specified, the results include the Cartesian product of the possible valuesthe variables can take, making the for clause similar in spirit to the from clause of an SQL query. The let clause simply allows complicated expressions to be assigned to variable names for simplicity of representation. The where section, like the SQL where clause, performs additional tests on the joined tuples from the for section.

Finally, the return section allows the construction of results in XML. A simple FLWR expression that returns the account numbers for checking accounts is based on the XML document of Figure , which uses ID and IDREFS:

for $x in /bank-2/account let$acctno := $x/@account-number where$x/balance > 400
return <account-number> $acctno </account-number> Since this query is simple, the let clause is not essential, and the variable$acctno in the return clause could be replaced with $x/@account-number. Note further that, since the for clause uses XPath expressions, selections may occur within the XPath expression. Thus, an equivalent query may have only for and return clauses: for$x in /bank-2/account[balance > 400]
return <account-number> $x/@account-number </account-number> However, the let clause simplifies complex queries. Path expressions in XQuery may return a multiset, with repeated nodes. The function distinct applied on a multiset, returns a set without duplication. The distinct function can be used even within a for clause. XQuery also provides aggregate functions such as sum and count that can be applied on collections such as sets and multisets. While XQuery does not provide a group by construct, aggregate queries can be written by using nested FLWR constructs in place of grouping; we leave details as an exercise for you. Note also that variables assigned by let clauses may be set- or multiset-valued, if the path expression on the right-hand side returns a set or multiset value. Joins are specified in XQuery much as they are in SQL. The join of depositor, account and customer elements in Figure, which we wrote in XSLT , can be written in XQuery this way: for$b in /bank/account,
$c in /bank/customer,$d in /bank/depositor
where $a/account-number =$d/account-number
and $c/customer-name =$d/customer-name
return <cust-acct> $c$a </cust-acct>

The same query can be expressed with the selections specified as XPath selections:

for $a in /bank/account,$c in /bank/customer,
$d in /bank/depositor[account-number =$a/account-number
and customer-name = $c/customer-name] return <cust-acct>$c $a</cust-acct> XQuery FLWR expressions can be nested in the return clause, in order to generate element nestings that do not appear in the source document. This feature is similar to nested subqueries in the from clause of SQL .For instance, the XML structure shown in Figure , with account elements nested within customer elements, can be generated from the structure in Figure by this query: The query also introduces the syntax$c/*, which refers to all the children of the node, which is bound to the variable $c. Similarly,$c/text() gives the text content of an element, without the tags.

Path expressions in XQuery are based on path expressions in XPath, but XQuery provides some extensions (which may eventually be added to XPath itself). One of the useful syntax extensions is the operator ->, which can be used to dereference IDREFs, just like the function id(). The operator can be applied on a value of type IDREFS to get a set of elements. It can be used, for example, to find all the accounts associated with a customer, with the ID/IDREFS representation of bank information.

We leave details to the reader. Results can be sorted in XQuery if a sortby clause is included at the end of any expression; the clause specifies how the instances of that expression should be sorted. For instance, this query outputs all customer elements sorted by the name subelement:

for $c in /bank/customer, return <customer>$c/* </customer> sortby(name)
To sort in descending order, we can use sortby(name descending).

Sorting can be done at multiple levels of nesting. For instance, we can get a nested representation of bank information sorted in customer name order, with accounts of each customer sorted by account number, as follows.

XQuery provides a variety of built-in functions, and supports user-defined functions. For instance, the built-in function document(name) returns the root of a named document; the root can then be used in a path expression to access the contents of the document. Users can define functions as illustrated by this function, which returns a list of all balances of a customer with a specified name:

function balances(xsd:string $c) returns list(xsd:numeric) { for$d in /bank/depositor[customer-name = $c],$a in /bank/account[account-number=$d/account-number] return$a/balance
}

XQuery uses the type system of XMLSchema. XQuery also provides functions to convert between types. For instance, number(x) converts a string to a number. XQuery offers a variety of other features, such as if-then-else clauses, which can be used within return clauses, and existential and universal quantification, which can be used in predicates in where clauses. For example, existential quantification can be expressed using some $e in path satisfies P where path is a path expression, and P is a predicate which can use$e. Universal quantification can be expressed by using every in place of some.

The Application Program Interface

With the wide acceptance of XML as a data representation and exchange format, software tools are widely available for manipulation of XML data. In fact, there are two standard models for programmatic manipulation of XML, each available for use with a wide variety of popular programming languages.

One of the standard APIs for manipulating XML is the document object model (DOM), which treats XML content as a tree, with each element represented by a node, called a DOMNode. Programs may access parts of the document in a navigational fashion, beginning with the root. DOM libraries are available for most common programming langauges and are even present in Web browsers, where it may be used to manipulate the document displayed to the user.We outline here some of the interfaces and methods in the Java API for DOM, to give a flavor of DOM. The Java DOM API provides an interface called Node, and interfaces Element and Attribute, which inherit from the Node interface.

The Node interface provides methods such as getParentNode(), getFirstChild(), and getNextSibling(), to navigate the DOM tree, starting with the root node. Subelements of an element can be accessed by name getElementsByTagName(name), which returns a list of all child elements with a specified tag name; individual members of the list can be accessed by the method item(i), which returns the ith element in the list. Attribute values of an element can be accessed by name, using the method getAttribute( name). The text value of an element is modeled as a Text node, which is a child of the element node; an element node with no subelements has only one such child node. The method getData() on the Text node returns the text contents. DOM also provides a variety of functions for updating the document by adding and deleting attribute and element children of a node, setting node values, and so on.

Many more details are required for writing an actual DOM program; see the bibliographical notes for references to further information. DOM can be used to access XML data stored in databases, and an XML database can be built using DOM as its primary interface for accessing and modifying data. However, the DOM interface does not support any form of declarative querying.

The second programming interface we discuss, the Simple API for XML (SAX) is an event model, designed to provide a common interface between parsers and applications. This API is built on the notion of event handlers, which consists of user-specified functions associated with parsing events. Parsing events correspond to the recognition of parts of a document; for example, an event is generated when the start-tag isfound for an element, and another event is generated when the end-tag is found. The pieces of a document are always encountered in order from start to finish. SAX is not appropriate for database applications.

Storage of XML Data

Many applications require storage of XML data. One way to store XML data is to convert it to relational representation, and store it in a relational database. There are several alternatives for storing XML data, briefly outlined here.

Relational Databases

Since relational databases are widely used in existing applications, there is a great benefit to be had in storing XML data in relational databases, so that the data can be accessed from existing applications.

Converting XML data to relational form is usually straightforward if the data were generated from a relational schema in the first place, and XML was used merely as a data exchange format for relational data. However, there are many applications where the XML data is not generated from a relational schema, and translating the data to relational form for storage may not be straightforward. In particular, nested elements and elements that recur (corresponding to set valued attributes) complicate storage of XML data in relational format. Several alternative approaches are available:

• Store as string. A simple way to store XML data in a relational database is to store each child element of the top-level element as a string in a separate tuple in the database. For instance, the XML data in Figure could be stored as a set of tuples in a relation elements(data), with the attribute data of each tuple storing one XML element (account, customer, or depositor) in string form.

While the above representation is easy to use, the database system does not know the schema of the stored elements. As a result, it is not possible to query the data directly. In fact, it is not even possible to implement simple selections such as finding all account elements, or finding the account element with account number A-401, without scanning all tuples of the relation and examining the contents of the string stored in the tuple.

A partial solution to this problem is to store different types of elements in different relations, and also store the values of some critical elements as attributes of the relation to enable indexing. For instance, in our example, the relations would be account-elements, customer-elements, and depositor-elements, each with an attribute data. Each relation may have extra attributes to store the values of some subelements, such as account-number or customer-name. Thus, a query that re