Databases Reference
In-Depth Information
data (without loss) via the chase. In general, this recovery is up to homomorphic
equivalence due to the presence of nulls; in the ideal case when the original source
instance is recovered exactly, we call the chase-inverse an
exact
chase-inverse. The
second type of operational inverses, which we call
relaxed chase-inverses
,
1
are
relaxations of chase-inverses that work in situations where there is information loss
and, hence, chase-inverses do not exist. Intuitively, a relaxed chase-inverse recovers
the original source data as well.
In this chapter, we use various concrete examples of schema evolution to illus-
trate the main developments and challenges behind composition and inversion and
their applications to schema evolution. We note that we are focused here on com-
position and inversion; a companion topic chapter [
Hartung et al. 2011
] will give a
separate overview of the schema evolution area in general. In our survey, we illus-
trate the concept of composition, and then discuss the two flavors of operational
inverses mentioned above. At the same time, we discuss the languages in which
such composition and inversion can be expressed. In the context of the schema evo-
lution scenarios that we consider, these languages vary in complexity from GAV
schema mappings to LAV and GLAV schema mappings (the latter are also known as
source-to-target tuple-generating dependencies, or s-t tgds [
Fagin et al. 2005a
]) and
then to mappings specified by second-order (SO) tgds [
Fagin et al. 2005b
]. During
the exposition, we will proceed from simpler, easier scenarios of schema evolu-
tion to more challenging scenarios, and illustrate how composition and inversion
techniques can be put together into a framework that deals with schema evolution
problems.
In a separate section, we examine in detail two systems that implement one or
both of the above schema mapping operators to deal with aspects of schema evo-
lution. The first one is an implementation of mapping composition [
Yu and Popa
2005
] that is part of the Clio system is based on the SO tgds introduced in
Fagin et al.
[
2005b
] and is specifically targeted at the problem of mapping adaptation in the con-
text of schema evolution. The second system is the PRISM workbench [
Curino et al.
2008
] for query migration in the presence of schema evolution. This system is based
on query rewriting under constraints and in particular on the chase and backchase
framework [
Deutsch et al. 1999
]. However, before it can apply such query rewriting,
the PRISM system needs to implement both mapping composition and inversion.
The notion chosen here for inversion is based on quasi-inverses [
Fagin et al. 2008b
].
We end the paper with a discussion of the main open research questions that
still remain to be solved. Perhaps the most important open issue here is to find a
unifying schema-mapping language that is closed under both composition and the
various flavors of inverses, and, additionally, has good algorithmic properties.
1
These were introduced in
Fagin et al.
[
2009b
] under a different name:
universal-faithful inverses
.
However, the term
relaxed chase-inverses
, which we use in this paper, is a more suggestive term
that also reflects the relationship with the chase-inverses.
