Databases Reference
In-Depth Information
chase and backchase algorithm.
q
1
.s;c/ W
Student
.s; “CS”/ ^
Enrolled
.s;c/:
M
0
1
The above quasi-inverse
M
1
. In general,
however, quasi-inverses differ from chase-inverses (or relaxed chase-inverses), and
one may find quasi-inverses with nonintuitive behavior (e.g., a quasi-inverse that
is not a chase-inverse, even when a chase-inverse exists). We note that the PRISM
development preceded the development of chase-inverses or relaxed chase-inverses.
We also remark that the language needed to express quasi-inverses requires dis-
junction. As a result, PRISM uses an extension of the chase and backchase algorithm
that is able to handle disjunctive dependencies; this extension was developed as part
of MARS [
Deutsch and Tannen 2003
]. Finally, we note that we may not always
succeed in finding equivalent reformulations, depending on the input query, the evo-
lution mappings and also on the quasi-inverses that are chosen. Hence, PRISM must
still rely on a human DBA to solve exceptions.
also happens to be a chase-inverse of
7
Other Related Work
We have emphasized in this paper the operational view of schema evolution, where
a schema mapping
is viewed as a transformation, which given an instance I
produces
chase
M
.I/. Under this view, we have emphasized two types of opera-
tional inverses: the chase-inverse (with its exact variation), which corresponds to
the absence of information loss, and the relaxed chase-inverse, which is designed for
the case of information loss. However, there is quite a lot of additional (and related)
work on mapping inversion that studies more general, nonoperational notions of
inverses. These notions can be categorized into three main notions: inverses [
Fagin
2007
], quasi-inverses [
Fagin et al. 2008b
], and maximum recoveries [
Arenas et al.
2008
].
Most of the technical development on inverses, quasi-inverses, and maximum
recoveries was originally focused on the case when the source instances were
assumed to contain no nulls, that is, they were assumed to be ground. However,
in practice, such an assumption is not realistic, since an instance with nulls can
easily arise as the result of another schema mapping. This is especially true in
schema evolution scenarios, where we can have chains of mappings describing
the various evolution steps. To uniformly deal with the case where instances can
have nulls, the notions of inverses and of maximum recoveries were extended
in
Fagin et al.
[
2009b
] by systematically making use of the notion of homomorphism
between instances with nulls as a replacement for the more standard containment of
instances. In addition to their benefit in dealing with nonground instances, it turns
out that the two extended notions, namely extended inverses and maximum extended
recoveries, have the operational counterpart that we want. More concretely, when
M
M
is a GLAV mapping, we have that: (1) extended inverses that are also expressed as
GLAV mappings coincide with chase-inverses, and (2) maximum extended recover-
