Database Reference
In-Depth Information
We restate it in the XML context as follows:
r
r
−−−→
FLIGHT
GEO
SERVES
t
1
t
2
t
city
country
city
country
phone
src
airl
airl
y
y
u
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.
x
x
z
x
z
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-
