Proposition 20.28 (1) There exists a mapping specified by a finite set of st-tgds that is
not quasi-invertible but has a maximum recovery.
(2) For every mapping
that is total, closed-down on the left and quasi-invertible, there
exists a mapping that is a maximum recovery of
M is a maximum
M is a quasi-inverse and recovery of
if and only if
Note that part (1) of this proposition has already been proved in Proposition 20.27 .
Given that inverses and quasi-inverses are not guaranteed to exist for the class of map-
pings specified by st-tgds, we study in Sections 20.1 and 20.1 the decidability of invert-
ibility and quasi-invertibility for this class of mappings. On the other hand, the problem of
verifying whether a mapping
has a maximum recovery becomes trivial in this context,
as every mapping specified by this class of dependencies admits a maximum recovery.
Thus, we only consider here the fundamental problem of verifying, given mappings
M specified by st-tgds, whether
M is a maximum recovery of
. Somewhat sur-
prisingly, not only is this problem undecidable, but also the problem of verifying whether
M is a recovery of a mapping
Theorem 20.29 The problem of verifying, given mappings
=(R 1 , R 2 ,
12 ) and
M is a recovery (maximum
(R 2 , R 1 ,
21 ) with
21 finite sets of st-tgds, whether
recovery) of M is undecidable.
As we have mentioned in the previous sections, we are still missing the algorithms for com-
puting the inverse operators introduced in this chapter. In the next section, we present a uni-
fied algorithm for computing these operators, which uses some query rewriting techniques,
and takes advantage of the tight connections between the notions of inverse, quasi-inverse
and maximum recovery shown in Propositions 20.14 , 20.27 and 20.28 .
20.3 Computing the inverse operator
Up to this point, we have introduced and compared three notions of inverse proposed in the
literature, focusing mainly on the fundamental problem of the existence of such inverses.
Arguably, the most important problem about these operators is the issue of how to compute
them for the class of mappings specified by st-tgds. This problem has been studied for the
case of the notions of inverse, quasi-inverse and maximum recovery. In this section, we
present an algorithm for computing maximum recoveries of mappings specified by st-tgds,
which by the results of the previous sections can also be used to compute inverses and
quasi-inverses for this type of mapping. Interestingly, this algorithm is based on query
rewriting , which greatly simplifies the process of computing such inverses.
We start by introducing the notion of query rewritability over the source, which is similar
to the notion of rewritability introduced in Section 7.5 .Let
be a mapping from a schema
R 1 to a schema R 2 and Q a query over schema R 2 . Then a query Q is said to be a rewriting
of Q over the source if Q is a query over R 1 such that for every S
I NST (R 1 ), it holds