Databases Reference
In-Depth Information
second one is that of solving the actual
data exchange problem
; originally formal-
ized in
Fagin et al.
[
2005a
], this consists in assigning a clear semantics to a given
set of mappings, to turn them into executable queries on the source, and updates on
the target that generate the desired target instance.
Another important application of schema mappings is query answering [
Abite-
boul and Duschka
1998
]. In particular, given a fixed data exchange scenario, target
query answering aims at computing the set of answers to a query posed on the target
schema. In our example, this amounts to take a query initially expressed on the target
tables in Fig.
5.1
b, and to reformulate it according to the source tables in Fig.
5.1
a.
In recent years, research on schema mappings, data exchange, and query answer-
ing have provided quite a lot of building blocks toward this goal. Interestingly,
the majority of bulk theoretical ideas for solving the data exchange problem were
introduced several years after the first mapping generation techniques had been
developed. The main motivation was that of providing a clear theoretical founda-
tion for schema mappings, i.e., a solid formalism that systems could use to reason
about mappings and their properties, to optimize them, and to guarantee that data
are exchanged in an optimal way.
In the following sections, we provide an overview of these contributions. More
specifically:
Section
2
provides an overview of data exchange theory, and more specifically
of the notions of dependencies, mapping scenario, and solution;
Section
3
introduces the seminal ideas about schema mapping generation, and
the early algorithms developed in the framework of the Clio project [
Miller et al.
2000
;
Popa et al. 2002
];
Section
4
describes the recent advancements in terms of schema mapping rewrit-
ing techniques that were introduced to improve the quality of solutions;
Section
5
provides an overview of the complexity results and algorithms devel-
oped for query answering over schema mappings;
Section
6
discusses a number of other interesting developments and applications
of schema mapping techniques;
Finally, Sect.
7
concludes the chapter by discussing the open problems in this
area.
2
Preliminaries
To provide a common formalism to be used across the chapter, we first introduce
the data model we adopt as a reference. Data exchange was originally formalized for
the relation model, so we focus on this data model. Nested sources will be discussed
separately in the following sections.
In all of the data exchange theory, databases are considered as collections of
relations on two distinct and disjoint domains: a set of
constants
,
CONST
,asetof
labeled nulls
,
NULLS
.
Labeled nulls
are used during the generation of solutions to
“invent” new values in the target that do not appear in the source database. One way
