Database Reference
In-Depth Information
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
M
is a maximum
M
and, moreover,
M
is a quasi-inverse and recovery of
recovery of
M
if and only if
M
.
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
M
M
specified by st-tgds, whether
M
is a maximum recovery of
and
. Somewhat sur-
prisingly, not only is this problem undecidable, but also the problem of verifying whether
a mapping
M
M
is a recovery of a mapping
M
.
M
=
Theorem 20.29
The problem of verifying, given mappings
M
=(R
1
,
R
2
,
Σ
12
)
and
M
is a recovery (maximum
(R
2
,
R
1
,
Σ
21
)
with
Σ
12
and
Σ
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
M
∈
I
NST
(R
1
), it holds
