Databases Reference
In-Depth Information
Schema evolution
M
1
M
2
Schema
S
2
Schema
S
1
Schema
S
M
¢
1
M
¢
2
q
1
q
2
q
Query rewriting
Fig. 7.7
Schema evolution and query rewriting in PRISM
and others. These operations are chosen carefully so that they represent the most
common forms of schema evolution that arise in practice, but also to allow for invert-
ibility. More precisely, each of the evolution mappings that are allowed in PRISM
is guaranteed to have a quasi-inverse [
Fagin et al. 2008b
]. Thus, in Fig.
7.7
,
M
0
1
M
0
2
is a quasi-inverse of
M
2
. The main reason for
why each evolution mapping must have a reverse mapping is that the presence of
mappings in both directions (i.e., from
S
to
S
1
, and from
S
1
to
S
) is essential for the
application of query reformulation algorithms, as we explain next.
More concretely, query reformulation in PRISM can be phrased as follows. We
are given a query q over the original schema
S
. We assume one step of evolution,
with mapping
M
1
,and
is a quasi-inverse of
M
1
from
S
to
S
1
and reverse mapping
M
0
1
from
S
1
to
S
. The problem
is to find a query q
1
over the schema
S
1
such that q
1
is equivalent to q,where
equivalence is interpreted over the union
S
[
S
1
of the two schemas and where
M
1
M
0
1
and
form constraints on the larger schema. In other words, we are looking for
a query q
1
to satisfy q.K/ D q
1
.K/, for every instance K over
S
[
S
1
such that K
satisfies the union of the constraints in
M
0
1
. In turn, this is an instance of
the general problem of query reformulation under constraints [
Deutsch et al. 2006
],
which can be solved by the chase and backchase method [
Deutsch et al. 1999
].
The application of the chase and backchase method in this context consists of, first,
applying the chase on q with the constraints in
M
1
and
M
1
, and then on applying the (back)
M
0
1
chase with the reverse constraints in
to find equivalent rewritings of q.
Before we concretely illustrate on an example the application of the chase and
backchase in the PRISM context, we need to point out that for multiple evolution
steps, the query reformulation problem needs to take into account all the direct and
reverse mappings alongs the chain (e.g.,
M
0
1
M
0
2
for two evolu-
tion steps). Thus, as the evolution chain becomes longer, the number of constraints
involved in query reformulation becomes larger. To reduce the number of constraints
needed for rewriting, PRISM makes repeated use of composition to replace two
consecutive schema mappings by one schema mapping. Since PRISM restricts map-
pings such as
M
1
,
M
2
,
,and
M
1
and
M
2
to always be GAV schema mappings, the composition
M
1
ı
M
2
can also be expressed as a GAV mapping (see our earlier Theorem
1
,
