We restate it in the XML context as follows:
That is, if we have tuples in FLIGHT and GEO that agree on the values of the source and
city attributes, we grab the values of the airline and country attributes, invent a new
value u for phone and create a tuple in relation SERVES .
The rules of XML schema mappings are thus represented via tree patterns . Essentially,
they say that if a certain pattern occurs in a source document, some other pattern, obtained
by its restructuring, must occur in the target.
This view of XML schema mappings is not surprising if we note that in our relational
examples, the rules are obtained by using a relational pattern - i.e., a conjunction of source
atoms - and rearranging them as a conjunction of target atoms. Conjunctions of atoms are
natural analogs of tree patterns. Indeed, the pattern on the right-hand side of the above
rule, for example, can be viewed as the conjunction of the statements about existence of
the following edge relations: between the root and a node labeled SERVES , between that
node and a node labeled t , between the t -node and nodes labeled airl , city , country ,
and phone , respectively, and between those nodes and nodes carrying attribute values y , x ,
z ,and u .
Of course we shall see when we describe XML data exchange that patterns could be
significantly more complicated: they need not be simple translations of relational atoms. In
fact one can use more complicated forms of navigation such as the horizontal ordering of
siblings in a document, or the descendant relation. But for now our goal was to introduce
the idea of tree patterns by means of a straightforward translation of a relational example.
1.2 Overview of the main tasks in data exchange
The key tasks in many database applications can be roughly split into two groups:
1. Staticanalysis.This mostly involves dealing with schemas; for example, the classical re-
lational database problems such as dependency implication and normalization fall into
this category. Typically, the input one considers is (relatively) small, e.g., a schema or
a set of constraints. Therefore, somewhat higher complexity bounds are normally toler-