Databases Reference
In-Depth Information
M
ı
M
0
(since
0
is chase-equivalent but not logically equivalent to , which expresses
M
ı
M
0
). Such relaxation of composition appears early in the work of Madhavan
and Halevy [
Madhavan and Halevy 2003
].
4
The concept used there is based, implic-
itly, on CQ-equivalence; however, their results are limited to GLAV mappings,
which, in general, are not powerful enough to express composition (even under the
relaxed form) [
Fagin et al. 2005b
].
Since schemas can be quite large in practice, mapping composition as well as
mapping reduction can be expensive. Therefore, a great deal of the work in
Yu a n d
Popa [
2005
] is spent on developing pruning techniques that identify the parts of a
schema mapping that are not affected by the changes in the schemas, and hence do
not need to be involved in the process of composition and reduction. We refer the
interested reader to
Yu and Popa
[
2005
] for more details on this.
We also note that
0
represents a relaxation of the composition
6.2
The PRISM Workbench: Query Adaptation
The PRISM project, described in
Curino et al.
[
2008
], has the overall goal of
automating as much as possible the database administration work that is needed
when schemas evolve. Under this general umbrella, one of the main concrete goals
in PRISM is to support migration (or adaptation) of queries from old (legacy)
schemas to the new evolved schemas. Similar to the Clio-based schema evolution
system in
Yu and Popa
[
2005
], PRISM also uses schema mappings (although in a
restricted form) to describe the evolution of schemas. However, differently from the
Clio-based system, the focus in PRISM is not on mapping adaptation but on query
adaptation. More concretely, in the Clio-based system, we are given a schema map-
ping from
S
to
T
and the goal is to adapt it when either
S
or
T
changes, while
in PRISM we are given a query q over a schema
S
and the goal is to adapt it
when
S
changes. Because it is targeted at queries, PRISM makes prominent use
of query rewriting. In particular, it applies the chase and backchase algorithm intro-
duced in
Deutsch et al.
[
1999
] for query rewriting under constraints. Additionally,
PRISM also makes use of the schema mapping operations that we described ear-
lier (i.e., composition and inversion) to enable the application of the query rewriting
algorithm and to optimize its application.
We u s e F i g .
7.7
to illustrate the type of functionality that PRISM aims to achieve.
There, schema
S
represents an initial (legacy) schema that goes through several
steps of change, forming a schema evolution chain: from
S
to
S
1
,thentoS
2
,and
so on. Each of the evolution steps can be described by a mapping. However, these
mappings are not arbitrary and must correspond to a set of predefined schema modi-
fication operations (SMOs) that allow only for certain type of schema modifications.
Examples of such modifications are: copying of a table, renaming of a table or of
a column, taking the union of two tables into one, decomposing a table into two,
4
In fact, that is how Madhavan and Halevy defined composition of schema mappings.
