Databases Reference
In-Depth Information
Schema S
Schema S
1
Student
Takes
sid
major
sid
major
M
1
course
Enrolled
sid
course
q (s,c) :- Takes(s,“CS”,c)
Fig. 7.8
Example of schema evolution with a query to be rewritten
M
0
1
part 1). The same cannot be done for the reverse schema mappings (e.g.,
M
0
2
and
), which are quasi-inverses of the direct mappings, and require in general
a more complex language that includes disjunction (see
Fagin et al. 2008b
). The
exact language in which to express composition of such schema mappings (i.e.,
with disjunction) is an open research problem.
To make the above ideas more concrete, consider the following schema evolution
example shown in Fig.
7.8
. This example is based on two of our earlier schemas (see
S
and
T
in Fig.
7.2
). Here, the schema
S
represents the “old” schema, which then
evolves into a “new” schema
S
1
. The evolution step from
S
to
S
1
can be described
by one of the SMOs that the PRISM workbench allows. In particular, this evolution
step is an application of the
Decompose
operator where the table
Takes
is split
into two tables
Student
and
Enrolled
that share the common attribute
sid
.
The application of the
Decompose operator
in this case can be represented by
the following GAV mapping (this is the same as the earlier
M
in Sect.
3
):
M
1
W
Takes
.s;m;
co
/ !
Student
.s;m/
Takes
.s;m;
co
/ !
Enrolled
.s;
co
/:
Assume now that we have a legacy query q that is formulated in terms of the old
schema. This query, shown in Fig.
7.8
, retrieves all pairs of student id and course,
where the major is “CS.” The goal is to adapt, via query rewriting, the query q into
a new query q
1
that is formulated in terms of the new schema
S
1
and is equivalent
to q.
The first step is to retrieve a quasi-inverse
M
0
1
M
1
. As mentioned earlier, each
evolution step in PRISM is an instance of one of the predetermined SMOs. Thus, a
quasi-inverse always exists and can be chosen by the system or by the user. In this
case, the following is a quasi-inverse of
of
M
1
:
0
1
W
Student
.s;m/ ^
Enrolled
.s;
co
/ !
Takes
.s;m;
co
/:
M
The next step is to apply the chase and backchase algorithm to find rewritings of q
that are equivalent given the union of the constraints in
M
0
1
. The following
query over schema
S
1
is such an equivalent rewriting and will be returned by the
M
1
and
